잘못된 코드

import sys
input = sys.stdin.readline

G = int(input())
P = int(input())
arr = (True)* G
g = ()
ans = 0
for _ in range(P):
    g.append(int(input()))
    
for i in range(0,len(g)):
    req1 = g(i)
    sig=0
    for j in range(req1-1,-1,-1):
        if(arr(j)==True):
            arr(j)=False
            ans+=1
            sig=1
            break
    if(sig==0):
        print(ans)
        exit()

처음으로 생각한 코드입니다.

그런데 이 코드는 무차별 대입에 가깝기 때문에 시간복잡도가 너무 높고 실제로 백준이에게 제출했을 때도 타임아웃이 나왔다.

---

암호

import sys
input = sys.stdin.readline

def solve(n):
    if(reps(n) == n):
        return n
    reps(n) = solve(reps(n))
    return reps(n)

G = int(input())
P = int(input())
ans=0
reps = (i for i in range(G+1)) #게이트
for _ in range(P):
    n = int(input())
    a = solve(n)
    if(a== 0):
        break
    reps(a) = reps(a-1) #도킹을 하고 가장 큰 도킹 가능한 값으로 가야함
    ans+=1
print(ans)

위의 코드는 union-find 알고리즘을 사용합니다.

디스조인트 세트라고도 하는 유니온 찾기는 이를 사용하여 시간 복잡도를 크게 줄입니다.

리뷰 및 솔루션

솔직히 이해하는 데 꽤 시간이 걸렸고 Union Finder라는 문제라는 것을 알고 문제 해결에 통합하려고 시도했지만 실패했습니다.

그래서 구글링을 하고 최대한 이해하는데 집중했습니다.

게이트에 들어갈 때는 먼저 들어갈 수 있는 가장 높은 번호의 게이트로 들어가야 합니다.

위의 문제 예 1을 예로 들어 보겠습니다.

4 3 4 1 1

(게이트 수 + 1)만큼 reps라는 배열을 만듭니다.

그 다음에,

반복 (0) = 0

반복 (1) = 1

담당자 (2) = 2

담당자 (3) = 3

담당자 (4) = 4

생성되었을 것입니다.

4번 비행기가 먼저 들어왔으니 4번 게이트에 넣으세요.

비행기는 이제 4번 게이트로 들어갈 수 없겠죠?

그러면 다른 4번 비행기가 날아오더라도 4번 게이트가 아닌 3번 게이트를 통과하게 됩니다.

여기 조합 찾기의 개념이 사용됩니다.

reps(4) 값을 3으로 설정변경하는 것입니다

그 다음에 반복(0) = 0, 반복(1) = 1, 반복(2) = 2, 반복(3) = 3, 반복(4) = 3.

비행기 1이 도착하면 (0 0 2 3 3).

다음 평면 1이 도착하면 reps(1) = 0이므로 더 이상 평면을 도킹할 수 없습니다.

즉, reps(n)의 값이 0이면 응답을 반환하고, 0이 아니면 도킹할 수 있는 항공기의 수가 1씩 증가합니다.

ps 시간 복잡도: O(P log G)