소스 코드

import sys
input = sys.stdin.readline

def find(x):
    if parent[x] == x:
        return x
    
    parent[x] = find(parent[x])
    return parent[x]

def union(origin, sub):
    root_origin = find(origin)
    root_sub = find(sub)

    if root_origin == root_sub:
        return False
    
    parent[root_origin] = root_sub
    return True

G = int(input().rstrip())
P = int(input().rstrip())

# idx번 게이트의 대체 게이트는 value번 게이트
# value번 게이트도 또 다른 대체 게이트가 있을 수 있음. 연쇄적임
parent = [g for g in range(G + 1)]
result = 0

for _ in range(P):
    g = int(input().rstrip())
    g_sub = find(g) # g번 게이트의 대체 게이트 (g번이 아직 가능하다면 g번일 수 있음)

    if g_sub == 0: # 대체 게이트가 0번이란 것은 도킹이 불가능하다는 것을 의미
        break

    # 대체 게이트 g_sub에 도킹했으니, 이제 g_sub 게이트의 대체 게이트는 g_sub-1 번 게이트임
    # 만약 g_sub-1번 게이트가 이미 사용되어 대체 게이트가 있다면, g_sub도 그걸 대체 게이트로 삼게됨(유니온 파인드 원리)
    union(g_sub, g_sub - 1)
    result += 1

print(result)

풀이 요약

1. 기본적으로 n번 게이트까지들 중에 하나에 도킹하려할 때, 가장 숫자가 높은 것을 우선적으로 도킹을 시도한다(n번 게이트). 그래야 그보다 하위 숫자가 입력으로 들어왔을 때, 가능한 게이트 수에서 손해를 발생시키지 않는다.

2. 위 방식대로, 4번 게이트까지 중 하나에 도킹하려할 때, 4번 게이트에 도킹을 시도한다. 만약 이미 다른 비행기가 있다면, 4번 게이트의 대체 게이트를 -1한 값인 3번 게이트로 지정한다. 만약 3번 게이트가 이전에 도킹됐던 비행기가 있는 상태라서 3번 게이트의 대체 게이트가 2번 게이트로 지정된 상태라면, 4번 게이트의 대체 게이트도 2번 게이트가 된다.

3. 위 로직을 유니온 파인드 자료구조로 쉽게 구현할 수 있다. i번 게이트의 대체 게이트를 parent[i]번 게이트로 삼는다. 만약 대체 게이트가 0번이라면 이는 도킹이 불가능함을 의미한다.

4. 입력받는 희망 게이트 g에 대해, 우선 find(g)로 대체 게이트를 찾아본다. 만약 g번이 가능한 상태라면 대체 게이트는 그 자신인 g번일 것이다.

   만약 대체 게이트 g_sub가 0번이라면 조건에 따라 수행 종료이다.

   그렇지 않다면 그 게이트에 도킹시키고, g_sub번 게이트를 사용한 셈이므로, g_sub의 대체 게이트를 g_sub-1의 대체 게이트로 지정해준다. (union)

   역시 마찬가지로 g_sub-1 번 게이트가 사용가능한 상태라면, g_sub-1 번 게이트의 대체 게이트는 본인이고, g_sub의 대체 게이트 또한 g_sub-1 번 게이트가 된다.

어려웠던 점, 배운 점

• 규칙을 찾아보고 구현으로 해보려고 했지만, 죄다 TLE가 나는 풀이들이었다. 결국 적혀있는 유형처럼 유니온 파인드로 풀어보려고 했는데, 도저히 아이디어가 안 떠올라서 다른 사람 풀이를 참고했다. 골드 문제를 여럿 풀면서 느끼는건데, 골드 2 이상의 문제부터는 풀이의 핵심 아이디어를 떠올리기가 정말 어려운 것 같다..