백준 10775 공항

문제링크 : https://www.acmicpc.net/problem/10775

문제 추상화

• 문제가 잘 이해가 안되서 한참을 해석했다.
  • 각 비행기가 1~gi에 도킹
  • 이때 최대한 도킹할 수 있는 개수 구하기

아이디어

• 모든 경우 탐색
  • 각 비행기를 모든 게이트에 주차할 수 있는지 확인
  • 모든 게이트(G) * 비행기수(P) : G*P = 1e10 > 시간초과
    • 각 게이트가 빈 게이트를 바라보도록 함
  • union-find
  • p 배열 : 각 게이트보다 작은 게이트 중 비어있는 값
  • p 배열의 0을 지시 : 더이상 주차할 게이트가 없음 >> 종료

시간복잡도 계산

• 모든 비행기에서 : O(G) = 1e5
• 게이트를 확인 : O(1)
• 게이트에 비행기 넣은후 이전 비어있는 게이트를 재확인 : O(1)

인트 계산

• p : 게이트 최대 값 : 1e5 > INT 가능

코드

#include <iostream>
 
using namespace std;
 
int p[100010];
int find(int v) {
    if(p[v] == v) return p[v];
    return p[v] = find(p[v]);
}
 
void merge(int v1, int v2) {
    v1 = find(v1);
    v2 = find(v2);
    p[v1] = v2;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int G,P; cin >> G >> P;
    int cnt=0;
    // 부모 배열 초기 셋팅
    for(int i=1; i<=G; i++) {
        p[i] = i;
    }
    
    for(int i=0; i<P; i++) {
        int gate; cin >> gate;
        
        // 게이트 비어있는 곳이 없을경우
        int parentGate = find(gate);
        if(parentGate == 0) {
            break;
        }
        
        // 비어있는 게이트가 있을 경우
        cnt++;
        merge(parentGate, parentGate-1);
        
    }
    
    cout << cnt << '\n';
    
    
    
    return 0;
}
 

문제유형

• Union Find - 앞의 노드 중 비어있는 값 확인
  • 부모노드를 찾은 다음
  • 부모노드가 빈값이 없으면 종료
  • 빈값이 있을경우, 부모노드와 부모노드 이전값이랑 merge 수행