BOJ 10775 공항

📝 문제 정보

#

• 링크: https://www.acmicpc.net/problem/10775

🧐 관찰 및 접근

#

• 1번 게이트가 제일 쓰기 좋아보인다.
• 그러므로 1번 게이트를 아낀다고 생각하면, 모든 비행기를 도킹시킬때 갈 수 있는 최댓값으로 도킹시키면 되는 것 같다.
  • 이를 나이브하게 구현하면 한번당 $O(G)$가 걸릴 것이다.

    100000
    100000
    100000
    100000
    100000
    ...

    • 과 같은 테스트케이스를 생각해보면 된다.
• 따라서 $\text{calc}(g_i) = g_i$ 보다 작거나 같은 살아있는 게이트의 최댓값을 빠르게 찾으면 된다.
  • 이는 유니온파인드로 빠르게 수행 가능하다!
  • merge할때 자신보다 작은 값을 가리키게 하자.

💻 풀이

#

• 코드 (C++):

void solve(){
    int G, P; cin >> G >> P;
    UF.init(G+1);
    int ans = 0;
    while(P--){
        int g; cin >> g;
        int rt = UF.find(g);
        if(rt == 0) break;
        UF.merge(rt, rt-1);
        ans++;
    }
    cout << ans << "\n";
}