프로그래밍

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

[난이도] Gold2
[유형] Union-Find

[풀이]
어떤 비행기에게 g가 주어졌을 때 이 비행기는 1~g중 비어있는 아무 게이트에 도킹이 가능하다는 의미이다.
이때, g에 가까운 쪽에 도킹할수록 이후에 비행기들이 도킹하기에 유리하다는 것을 알 수 있다.
모든 비행기에 대해 g부터 1까지 검사하면서 빈 곳에 채우면 N이 10만이므로 O(N^2)이 되어 시간초과에 걸리게 된다.
이를 방지하기 위하여 union find 알고리즘을 이용해야 한다.
uf[G]를 선언한다. uf[i]의 의미는 어떤 비행기가 1~i번 게이트에 도킹해야할 때,
도킹해야하는 게이트의 index를 저장하는 배열로 생각할 수 있다.
만약 uf[i]!=i 라면 uf[i]는 root가 아니므로 uf[uf[i]]를 다시 탐색해야 한다.
이는 union find에서 흔히 사용하는 재귀를 이용한 find 함수로 구현할 수 있다.
재귀를 통해 uf[i]==i인 경우가 나오면 i를 return해준다.
uf[i]==i의 의미는 i에 도킹해야하는 비행기가 들어오면 i에 도킹하는것이 최적이라는 의미이다. 즉, i는 아직 도킹이 안되었다는 의미이다.
i가 return 되었으면 i에는 비행기가 도킹되게 되어 i에는 더이상 도킹할 수 있으므로
uf[i]를 i-1로 변경해준다.

만약 return된 i가 0이라면 도킹해야할 칸이 다 찼다는 의미이므로 반복문을 멈추고 지금까지 누적된 도킹 가능한 비행기 개수를 출력해주면 된다.

#include <cstdio>
const int mxN=1e5+1;
int uf[mxN],G,P;
int find(int n){
    if(n==uf[n]) return n;
    return uf[n]=find(uf[n]);
}
int main(){
    scanf("%d%d",&G,&P);
    for(int i=1;i<=G;i++) uf[i]=i;
    int ans=0;
    for(int i=1;i<=P;i++){
        int v;
        scanf("%d",&v);
        int k = find(v);
        if(k==0) break;
        uf[k]=k-1;
        ans++;
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/10775.cpp