[BOJ 10775, Python 3] 공항

[BOJ 10775, Python 3] 공항

반응형

https://www.acmicpc.net/problem/10775

풀이

그리디도 비슷한 유형의 문제들이 많이 보이네요.

일단 1번부터 g[i]번 게이트까지 영구적으로 도킹하려고 하면, 도킹할 수 있는 게이트의 최댓값을 찾아서 도킹해주는 것이 최적임을 알 수 있습니다. g[i]번부터 시작하여 1번까지 확인해보면서 도킹할 수 있는 곳에 도킹한다는 말입니다.

왜냐하면 만약 1~4번 게이트까지 도킹하는 비행기를 1번에 도킹하고, 1번 게이트만 도킹할 수 있는 비행기를 도킹하려고 하면 답은 2이지만, 1로 끝나기 때문입니다. 이렇게 g[i]번부터 확인해보면서 도킹할 수 있는 곳을 찾아가는 것이 최적해입니다.

하지만 g[i]번부터 1번게이트까지 확인하려면 G의 최댓값이 100,000이라서 비행기 한 개씩 g[i]번부터 1번부터 확인하는 O(N^2)풀이를 사용할 수 없습니다.

이때 O(N^2)과 똑같이 작동하면서 시간이 더 빠른 분리집합 / 유니온파인드 기법을 사용합니다.

부모 노드는 게이트 번호 자기 자신으로 설정하고, 합칠 때는 현재 도킹한 번호의 부모 노드를 [(현재 도킹한 번호 - 1)의 부모 노드]로 설정해주면 됩니다.

왜 이렇게 하냐면 만약 4, 2, 4, 4라는 입력값이 들어왔다고 해봅시다.

그러면 첫 번째는 find(4) = 4로 4번 게이트에 도킹을 했으니, merge(4, 3)을 통해 parent[4] = 3으로 바꿉니다.

두 번째 비행기도 도킹을 해야하는데 find(2) = 2로 나왔으니 2번 게이트에 도킹합니다. 그다음 merge(2, 1)를 하여 parent[2] =1로 바꿉니다

세 번째도 도킹을 할 때 find(4)를 하면 3이 나오니 3번에 도킹합니다. 그 후 merge(3, 2)를 하는데 parent[2] = 1이므로 parent[3] = 1로 설정됩니다.

마지막으로 4번이 들어오면 find(4) => 3 => parent[3] => 1로 1번 게이트에 도킹합니다. 그 후 merge(1, 0)을 해서 parent[2] = 1로 설정됩니다.

이후에 또 4이하의 값을 가진 비행기가 들어오면 find(x)를 할 때 0이 나오므로 더 이상 도킹을 할 수 없어서 종료하고 답을 출력하게 됩니다.

유니온 파인드로 이렇게 할 수 있다니 신기하네요.

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 def find(x): if x = = parent[x]: return x parent[x] = find(parent[x]) return parent[x] def merge(x, y): x = find(x) y = find(y) parent[x] = y input = __import__( 'sys' ).stdin.readline g = int (input()) p = int (input()) parent = [i for i in range (g + 1 )] airplane = [ int (input()) for _ in range (p)] ans = 0 for x in airplane: val = find(x) if val > 0 : ans + = 1 merge(val, val - 1 ) else : break print (ans) Colored by Color Scripter cs

반응형

from http://hello70825.tistory.com/298 by ccl(A) rewrite - 2021-08-16 16:26:34