풀이
Greedy
순서대로 들어오는 비행기에 대해 최대한 많은 비행기를 매칭시켜야 한다.
만약 순서대로 들어오는 비행기 중 한대가 매칭이 불가능 하다면 공항이 폐쇄되기 때문에 탐색을 중단해야 한다.
그렇다면, 비행기를 최대로 매칭시키는 방법은 뭘까?
비행기는 1 ~ g 번째 게이트 중 어디든지 도킹하면 된다.
하지만, 최대한 많은 비행기를 도킹하기 위해서는 g번 게이트에 가깝게 비행기를 도킹함으로써 다른 비행기가 확률적으로 도킹을 하게될 낮은 번호를 피하는 방법이다.
위의 그림을 보면 모든 비행기가 1 ~ gi번 게이트라는 선택지가 주어졌기에 최대한 높은번호를 선택해야 많은 비행기가 도킹 가능하다.
그렇다면 어떻게 최대한 높은 번호의 게이트를 찾을까?
단순한 방법으로 gi부터 1번 게이트까지 이미 도킹중인지 살핀다면 시간초과가 발생할 것이다.
좀 더 효율적인 방법이 필요하다.
g번 게이트에 접근할 때 이미 도킹되었다면, g - jump[g]번 게이트로 도킹을 시도하도록 알려주는 방법으로 해결했다.
맨 처음에는 g번 게이트에 도킹이 가능하기 때문에 jump는 0으로 초기화해주자.
그 다음 g를 입력받고, 비어있는 게이트의 경우에는 아래와 같이 jump와 도킹 비행기 수 cnt를 증가시켜주자.
만약 게이트에 이미 비행기가 도킹되어 있다면, jump배열을 갱신해 줄 필요가 있다.
소스코드
출처
10775번: 공항
예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 21591] Laptop Sticker [Python] (0) | 2023.07.07 |
|---|---|
| [백준 21633] Bank Transfer [Python] (0) | 2023.07.04 |
| [백준 20040] 사이클 게임 [Java] (0) | 2023.07.02 |
| [백준 4375] 1 [Java] (0) | 2023.06.29 |
| [백준 4195] 친구 네트워크 [Java] (0) | 2023.06.29 |