10775번 : 공항

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

10775번: 공항

 

 

문제

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

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

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

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

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

 

입력

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

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

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

 

출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

 

---

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int parent[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int g = Integer.parseInt(br.readLine());
        int p = Integer.parseInt(br.readLine());
        parent = new int[g + 1];
        for (int i = 0; i < g + 1; i++) {
            parent[i] = i;
        }

        int sum = 0;
        for (int i = 0; i < p; i++) {
            int x = Integer.parseInt(br.readLine());
            int gate = find(x);
            if(gate == 0) break;
            sum += 1;
            union(gate, gate - 1);
        }
        
        System.out.println(sum);
    }

    public static int find(int x) {
        if(parent[x] == x) return x;
        else return parent[x] = find(parent[x]);
    }

    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if(x<y) parent[y] = x;
        else parent[x] = y;
    }
}

 

해결방법

유니온 파인드(Union-Find) 알고리즘을 모르면 풀 지 못 하는 문제이다. 그래서 다른 블로그를 참고하였다.

 

비행기와 게이트가 최대 10만까지 갈수있으므로, 완전탐색으로 풀려할경우 GP번 반복하여 시간초과가 난다. 어떤 게이트에 비행기를 도킹시켜야하는지 찾아주는 연산을 유니온파인드를 이용해 최적화해야한다.

 

문제를 보면, Pi비행기는 1~Pi번째 게이트까지 도킹할수있다 나와있다.

끝 번호부터 도킹을 하는 이유는 다음과 같다. 만약 도착하는 순서대로 끝이 아닌 중간 혹은 첫 번호부터 도킹을 한다면 어떻게 될까? 만약 2 1로 도착한다면 뒤에 오는 비행기는 도킹을 하지 못한다. 따라서 끝 번호부터 도킹을 함으로써 먼저 도착하는 비행기를 최대한 마지막 번호(g)에  도킹시킴으로써 뒤에 올 비행기들에게 도킹할 수 있는 최대한 많은 범위(1 ~ g-1)를 줄 수 있다.

 

매 탐색마다 도킹이 안되어있는 게이트중 최대한 높은번호의 게이트를 찾을려면 O(NP)번 반복하여 시간초과가 난다. 이를 빠르게 하기 위해 유니온 파인드를 사용해 경로를 압축시켰다.

 

참고

https://steady-coding.tistory.com/114#google_vignette