백준) 10775 공항

10775 공항

문제

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

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

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

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

이렇게 공항을 운영할 경우 간혹 비행기가 어떤 곳에도 도킹하지 못하는 사고가 발생한다. 이러한 사고가 일어나면 공항의 평판이 급속히 나빠져, 이후 어떤 비행기도 도착하지 않으려 할 것이다.

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

입력

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

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

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

출력

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

예제 입력 

4
3
4
1
1

예제 출력 

2

예제 입력 2 

4
6
2
2
3
3
4
4

예제 출력 2 

3

1. 접근

비행기가 순차적으로 게이트에 도킹하며, 한 게이트에는 한 대만 도킹 할 수 있다.

비행기의 도착 게이트 번호(g)가 지정되면, 1번 부터 g번 까지 빈 게이트에 도킹할 수 있을 때, 최대한 많이 도킹시키고자 한다.

게이트를 노드로 생각하고, 간선은 이미 도킹된 게이트에 도착한 비행기의 차선책으로 생각해보면, 그래프적인 문제로 이해할 수 있다.

방 청소 문제 https://www.acmicpc.net/problem/9938 와 많이 비슷한 문제로, 디스조인트 셋을 활용해보자.

2. 풀이

비행기가 g번 보다 큰 게이트에는 도킹할 수 없다는 점을 주목하자.

직관적으로 최대한 많이 도킹시키려면 바로 g번 게이트에 도킹시키는게 효율적일 것이다.

비행기(g=2)과 비행기(g=1)가 주어진다면, 2번 게이트에 넣고, 1번 게이트에 도킹시켜야 둘다 도킹 시킬 수 있다.

방 청소 문제를 복기해보면, 간선을 비행기의 차선책을 나타내는 방법으로 사용했었다.

그러면 빈 노드를 find() 해보면 자신이 나올 것이고, 이미 도킹되어 있었으면 g보다 작은 게이트가 나올 것이다.

전략을 g가 비어있지 않으면 g-1에 도킹시키기기로 한다면, 여러 비행기들을 도킹시킨 후 새로운 비행기를 도킹시킬 때,

도킹 시킬 수 없음을 확인할 수 있는 방법은 무엇일까?

find(g)를 했을 때 0이 나오는지 확인하면 될 것이다. 현재 루트 노드는 차선책을 나타내고 있으므로, 0이 나온다면 도킹 불가능이다. 

3. 코드

#include <stdio.h>
using namespace std;
 
int g, p, a, i, cnt, empty_gate;
int parent[100001];
 
int find(int x) {
    if (x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}
 
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    parent[x] = y;
}
 
int main() {
    scanf("%d %d", &g, &p);
    for (i = 1; i <= g; ++i)
        parent[i] = i;
    for (i = 0; i < p; ++i) {
        scanf("%d", &a);
        empty_gate = find(a);
        if (empty_gate == 0)
            break;
        else {
            cnt++;
            unite(empty_gate, empty_gate - 1);
        }
    }
    printf("%d\n", cnt);
    return 0;
}