공항

백준 10775번: 공항

아이디어

기본적인 아이디어는 Greedy하게 남은 게이트 중 가장 번호가 큰 게이트에 도킹시키면 된다. 4를 입력받은 경우 4번 게이트가 남아있으면 4번, 없으면 3번, 3번도 없으면 2번.. 이런식으로 도킹하면 최대한 많이 도킹할 수 있다.

그런데 매번 입력받을 때마다 g(i)번부터 1번까지 자리가 있나 탐색을 할 수는 없는 노릇이다. 10만 * 10만이라 시간초과임. 유니온 파인드 자료구조를 통해 남은 자리가 어디인지 바로 알 수 있다!

우선 g(i)번에 도킹하는 경우 g(i)-1번과 유니온 연산을 진행한다. 숫자가 작은 쪽이 루트가 되도록 유니온 연산을 하면 된다. 이렇게 하나씩 연결하다 find(g)가 0인 경우 (즉 1번부터 g(i)번 게이트까지 꽉 찬 경우) 중단하고 답을 출력하면 된다.

코드

#include <bits/stdc++.h>

using namespace std;

int G, P;
int p[100001];

int find(int n) {
    if (p[n] < 0) return n;
    return p[n] = find(p[n]);
}

void Union(int n1, int n2) {
    n1 = find(n1);
    n2 = find(n2);
    if (n1 == n2) return;
    else {
        p[n2] = n1;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> G >> P;
    memset(p, -1, sizeof(p));
    int ans = 0;
    for (int i = 0; i < P; i++) {
        int g;
        cin >> g;
        if (find(g) == 0) break;
        Union(find(g)-1, find(g));
        ans++;
    }
    cout << ans << '\n';
    return 0;
}

여담

그리디처럼 생겼는데 유니온 파인드라니..