BOJ)10775 공항

문제: icpc.me/10775

비행기가 도착하는 순서대로 게이트에 도킹을 하는데 한 게이트에는 오직 한대의 비행기만 도킹이 가능하다

이때 각각의 비행기는 1~g번째 게이트중 하나에 도킹할 수 있다는 정보가 들어올 때 최대로 도킹할 수 있는 비행기의 수를 출력하면 된다.

g번째 게이트부터 도킹을 하는게 이득인 것임은 자명하므로 disjoint-set을 이용하여 g게이트에 도킹이 될 경우 다시 g게이트를 확인 할 때 g-1게이트를 확인 하도록 parent를 설정해주면 된다.

만약 find 호출에서 0을 호출하게 된다면 1~g번째 게이트는 모두 사용중인것이니 더 이상 도킹이 불가능 하므로 현재까지 도킹 된 횟수를 출력해 주면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
int par[100010], g, p, t, v, ans;
int find(int x) {
    if (x == par[x])return x;
    return par[x] = find(par[x]);
}
int main() {
    scanf("%d%d", &g, &p);
    for (int i = 0; i <= g; i++)
        par[i] = i;
    for (int i = 0; i < p; i++) {
        scanf("%d", &t);
        v = find(t);
        if (!v)break;
        par[v] = v - 1;
        ans++;
    }
    printf("%d\n", ans);
    return 0;
}