문제

[백준] 공항 (Gold 2)

요약

G개의 게이트, P개의 비행기가 있다. i번째 비행기를 1번부터 g(i)번째 게이트 중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항은 폐쇄된다. 최대 몇 개의 비행기가 도킹될 수 있는가?

분류

  • 그리디
  • 분리 집합

풀이

1. 내 풀이 (그리디 + 분리 집합)

  • i번째 비행기가 1번부터 g(i)번째 게이트에 도킹할 수 있다고 할 때, g(i)와 가까운 쪽의 게이트에 도킹하는 것이 유리하다.(그리디)
  • g(i)에서 가장 가깝고 비어있는 게이트를 바로 알기 위해 g(i)가 주어지면 도킹 가능한 가장 큰 게이트를 루트로 하는 트리를 그리자. (분리 집합)
  • 첫 번째 게이트에 비행기가 도킹될 때에 집중해 break point 를 생성하자.


import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

g = int(input())
p = int(input())
parent = [i for i in range(g)]


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


def union(s1, s2):
    if s1 > s2:
        parent[s1] = s2
    else:
        parent[s2] = s1


zero_flag = False
ans = 0
for _ in range(p):
    n = int(input()) - 1
    s1 = find(n)
    if s1 == 0 and zero_flag:
        break
    ans += 1

    if s1 != 0:
        union(s1, s1 - 1)
    else:
        zero_flag = True

print(ans)

2. DP

링크