백준 10775 공항

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

#include <iostream>
#include <algorithm>

using namespace std;

int parent[100001];

//i번 비행기는 1번 게이트부터 fly[i]번 게이트 중 하나에 영구적으로 도킹
int fly[100001];

int findParent(int k){
    return parent[k] == k ? k : parent[k]=findParent(parent[k]);
}

void uni(int a, int b){

    int pa = findParent(a);
    int pb = findParent(b);

    if (pa != pb) {
        parent[pa] = pb;
    }

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int g, p;
    int ans = 0;


    cin >> g >> p;


    for (int i = 1; i <= g; i++) {
        parent[i] = i;
    }

    for (int i = 1; i <= p; i++) {
        cin >> fly[i];

    }


    for (int i = 1; i <= p; i++) {

        int pf = findParent(fly[i]);

        if (pf == 0) {
            break;
        }

        uni(pf, pf - 1);

        ans++;
    }


    cout << ans;



    return 0;
}

1. 문제

게이트의 개수 g, 비행기의 개수 p가 주어지고, 각 비행기는 1부터 g[i]까지의 게이트 중 하나에 도킹을 하려고 한다. 1번 비행기부터 차례로 도킹하고, 해당 비행기가 어느 게이트에도 도킹을 할 수 없다면 그 즉시 공항이 폐쇄된다. 이 때, 도킹시킬 수 있는 최대 비행기의 수를 구하라.

2. 풀이

 i번 비행기가 g[i]의 게이트 번호를 초과하여 도킹할 수 없고, 도킹시킬 수 있는 최대 비행기를 구하는 문제이므로 비어있는 게이트 중 가장 게이트 번호가 큰 게이트에 해당 비행기를 도킹시키면 된다. 만약 g[i]가 차있다면, g[i]-1 게이트가 비어있는 지 검사하게 될 것이다. 게이트가 10만까지라 이를 일일이 확인하면 시간초과가 날 수 있으므로 다음과 같이 해결한다

    for (int i = 1; i <= g; i++) {
        parent[i] = i;
    }

 우선 parent 배열을 초기화한다.

    for (int i = 1; i <= p; i++) {

        int pf = findParent(fly[i]);

        if (pf == 0) {
            break;
        }

        uni(pf, pf - 1);

        ans++;
    }

 이후 입력받은 각 비행기의 g[i](fly[i])에 대해 parent를 찾는다. 이게 0이라면 g[i], g[i]-1, ..., 0까지 union되었다는 것이고,  g[i]까지의 게이트가 모두 차있다는 뜻이므로 공항을 폐쇄한다. fly[i]가 차있다면 fly[i]-1을 확인하여 넣게 될 것이므로 두 게이트를 union한다. 

 연산 결과로 나온 ans를 출력하면 정답을 구할 수 있다.