[BOJ] 10775 공항

date

Aug 25, 2023

slug

boj-10775

author

status

Public

문제 링크

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

문제

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

문제풀이

태그 보고 푼 문제

가장 많은 비행기를 공항에 도킹시켜야하지만, 상황을 가정해보자

3 → 3은 3, 2에 도킹가능하고

2 → 3은 2, 3에 도킹가능하다

3 → 2 → 1은 3, 2, 1에 도킹가능한데

1부터 차례대로 도킹하게 되면 1차례에 1에 도킹하지 못하는 상황이 발생한다.

그러므로

조건은 높은 순서를 가진 비행기는 최대한 높은 공항에 도킹시켜야한다

이를 만족시키기 위해서는

유니온-파인드 자료구조를 사용해서

p[비행기] = 공항 을 만족시키도록 분리-집합을 구성하면된다.

이때 비행기와 공항 번호가 같을경우 ( 자기자신에 도킹 )

비행기에서 하나 뺀것과 유니온 연산을 해서 다음 같은 번호가 올경우 하나 작은 공항에 도착시키도록 하면

그리디하게 최대로 공항에 도착시키도록 할 수 있다.

그리고 0번째 idx를 만들어 더이상 도착할 수 없는 경우를 따로 처리해준다.

파이썬 문제풀이 코드


import sys
input = sys.stdin.readline

G = int(input())
P = int(input())

arrival = []

p = [i for i in range(G+1)] 


for _ in range(P):
    arrival.append(int(input()))
    
    
count = 0

def find(node : int):
    if p[node] == node:
        return node
    
    p[node] = find(p[node])
    return p[node]

def union(a : int, b : int):  # a < b
    pa = find(a) 
    pb = find(b)
    
    p[pb] = pa 
def check():
    global count
    for idx in range(len(arrival)):
        airplane = arrival[idx]
        
        while True:
            if find(airplane) == 0:
                return
            if find(airplane) == airplane: # 자기자신에 도킹가능
                count += 1
                union(airplane-1, airplane) # 하나 뺸것과 유니온 해줌
                break
            
            else:
                airplane = find(airplane)
                
                
check()
print(count)

시간복잡도

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 10^5)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 10^5)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력

예제 입력

예제 출력

알고리즘 분류

자료 구조

그리디 알고리즘

분리 집합