문제 링크
https://www.acmicpc.net/problem/10775
접근 1 (오답)
처음에는 정렬을 이용해서 그리디 알고리즘으로 문제를 풀어보려고 했다.
어차피 이 문제에서 최대한 높은 번호의 게이트부터 차례대로 도킹시키면 되기 때문에 어떻게 잘 정렬만 한다면 풀 수 있을 것이라고 생각했기 때문이다.
G = int(input())
P = int(input())
p_info = [0 for _ in range(P + 1)]
li = [() for _ in range(P + 1)]
for i in range(1, P + 1):
gate_range = int(input())
p_info[i] = gate_range
li[i] = (gate_range, i)
li.sort()
def f():
for i in range(1, P + 1):
if i > li[i][0]:
return li[i][1] - 1
return i알고리즘은 간단한데, 먼저 게이트 도킹 가능 범위(문제에선 gi)를 gate_range 라고 정의했고, 리스트 li 에 (gate_range , 비행기 번호) 를 넣어주고 정렬한다.
그러면 gate_range가 짧은 비행기부터 순서대로 나올텐데, 정렬된 리스트 li의 인덱스 값이 gate_range 보다 큰 경우, 즉 gate_range 보다 앞서 도킹한 비행기의 수가 더 많으면 도킹을 할 수 없으므로 그 전 비행기까지는 도킹을 할 수 있다고 판단하여 그것을 반환하는 알고리즘이다.
그러나 정렬된 li에서 자신보다 앞 순서에 있다고 그 비행기가 먼저 도킹할 수 있는 것은 아니다. 예를들어 li = [(1,100),(2,1000),(3,500),(3,501),...] 과 같이 정렬되어있다고 치자. 알고리즘 상 i=4가 되었을 때 이 프로그램이 종료가 되지만 실제론 501번째 비행기를 도킹할 가능성이 있다. 왜냐하면 앞에있는 (2,1000) 은 사실 1000번째 비행기로 501번째 비행기가 도킹할 때에는 도킹이 되어있지 않기 때문이다....
이러한 문제점으로 오답이 떴다.
접근 2 (그리디)
p_info = [0 for _ in range(P + 1)]
gate_cnt = [0 for _ in range(G + 1)]
for i in range(1, P + 1):
p_info[i] = int(input())
def f():
for i in range(1, P + 1):
cur = p_info[i]
while cur > 0 and gate_cnt[cur]:
move = gate_cnt[cur]
gate_cnt[cur] += 1
cur -= move
if cur == 0:
return i - 1
gate_cnt[cur] += 1
return i
print(f())다음은 두번째 접근 방법이다.
이 방법은 "워프를 타는" 것과 비슷하다고 생각한다.
gate_cnt라는 리스트는 해당 게이트에 도킹을 시도한(또는 시도하려한) 개수를 카운트해준다.
gate_cnt[게이트] = 해당 게이트에 도킹하려고 한 횟수
예를 들어 설명하자면, 비행기의 입력이 100,100,100,100이라고 하자.
1번 비행기는 그냥 100번 게이트에 무리없이 도킹한다. 도킹했으므로 gate_cnt[100] = 1
2번 비행기도 100번 게이트에 도킹하려고 한다(gate_cnt[100]에 접근 시도, 이따가 값 올릴거임). 그런데 gate_cnt[100] = 1 을 보고 게이트 100에 이미 비행기가 있다는 것을 알 수 있다. 따라서 그 값 1만큼 이전의 게이트(99)를 노리게 되는 것이다. 결과적으로 99번 게이트에 도킹을 하고, gate_cnt[99] = 1 이 되고 gate_cnt[100]의 값도 하나 올려서 2가 되었다.
3번 비행기도 100번 게이트에 도킹하려고 한다(gate_cnt[100]에 접근 시도, 이따가 값 올릴거임). 그런데 gate_cnt[100] = 2 를 보고 게이트 100에 이미 비행기가 있다는 것을 알 수 있다. 따라서 그 값 2만큼 이전의 게이트(98)를 노리게 되는 것이다. 결과적으로 98번 게이트에 도킹을 하고, gate_cnt[98] = 1 이 되고 gate_cnt[100]의 값도 하나 올려서 3이 되었다.
이런식으로 계속해서 접근을 시도한 횟수를 카운트해서 바로 다음번 게이트를 찾을 수 있게 하는 방법이다.
정확한 시간복잡도는 모르겠지만 O(nlogn)정도 되는 것 같다...
접근 3 (Union-Find)
마지막은 Union-Find를 이용한 방법이다.
여기서는 최적화된 Find를 사용하지만 Union은 그냥 일반적인 Union이다.
def find(v):
if v == root[v]:
return v
root[v] = find(root[v])
return root[v]
def union(v1, v2): # v1 < v2
r1 = find(v1)
r2 = find(v2)
root[r2] = r1
G = int(input())
P = int(input())
root = [i for i in range(G + 1)]
ans = 0
for i in range(1, P + 1):
gate_range = int(input())
docking_loc = find(gate_range)
if docking_loc == 0:
break
ans += 1
union(docking_loc - 1, docking_loc)
print(ans)
root[i]에는 i번 게이트에 접근했을 때 도킹시킬 게이트의 위치를 알려준다. 그러므로 처음엔(그 어떤 비행기도 도킹하지 않았으므로) 게이트 자기 자신을 가리킨다.
만일 90번부터 100번까지 모두 도킹을 한 상황이라면 root[90~100]은 모두 89를 가리킨다. 이때 다음 비행기가 100번 게이트에 도킹을 시도하면, root[100] 이 가리키는 89로 가게 만든다. 그리고 이제 게이트 89는 먹혔으니(?) 88을 가리키게 만든다(이 과정이 union(docking_loc - 1, docking_loc))
