문제

10775번: 공항

풀이

큰 수의 비행기는 작거나 같은 수의 게이트에 도킹이 가능하다.
큰수의 비행기가 작은 수의 게이트에 먼저 도킹을 하게 되면 나중에 작은 수의 비행기가 그 게이트에 도킹을 못하게 되므로 비행기는 가능한 가장 큰 수의 게이트에 도킹해야 한다.

N 비행기가 N 게이트에 도킹을 했다면, 다음 N 비행기는 N-1 게이트에 도킹을 해야한다.
이렇게 이미 도킹되어 1 작은 게이트에 도킹해야 한다면 N과 N-1을 같은 집합으로 묶어 N이든, N-1이든 모두 N-1로 취급하여 처리하면 된다. 이때 Union-Find 알고리즘을 사용한다.

• 도킹할 게이트를 찾기 위해 find(N) 함수를 사용한다.
• 비행기가 N게이트에 도킹되면 N과 N-1을 같은 집합으로 merge(N, N-1) 한다.
  • 이때 항상 작은수가 root 가 되도록 하여 find 함수로 찾은 수가 항상 도킹 가능한 게이트가 되도록 한다.

만약 N-1 = 0 이라면 더이상 도킹 가능한 게이트가 없으므로 해당 번째를 출력하고 끝내면된다.

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> head;

int find(int x)
{
    if (head[x] == x)
        return x;
    
    return head[x] = find(head[x]);
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);

    if (x == y)
        return;

    if (x > y) // 문제의 조건때문에 작은놈이 항상 root 
        head[x] = y;
    else
        head[y] = x;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int g, p;
    cin >> g;
    cin >> p;

    head.resize(g+1);
    for (int i=0; i<g+1; ++i)
        head[i] = i;

    int cnt = 0;
    while(p--)
    {

        int gi;
        cin >> gi;

        int ptr = find(gi);
        if (ptr > 0)
        {
            ++cnt;
            merge(ptr, ptr-1);
        }
        else
            break;

    }

    cout << cnt << endl;
    return 0;
}