Boj 10775 c++ 공항

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

 

문제

 

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

 

 

문제를 이해해보면 

총 G개의 게이트가 주어지고, 하나의 게이트에는  하나의 비행기만 도킹할 수 있다.

각 비행기는 도킹할 수 있는 게이트의 범위가 숫자의 형태로 주어진다. ex) 4이면 1~4게이트에만 도킹할 수 있다.

비행기는 주어진 순서대로 도킹하며, 범위 내에서 더이상 도킹할 수 있는 게이트가 존재하지 않는다면 공항을 폐쇄한다.

 

문제만 읽어봤을 때는 어떻게 풀어야 할지 감도 잡히지 않았다.

막연하게 '각 비행기가 도킹할 수 있는 게이트의 범위를 집합으로 만들어야 하나... '와 같은 생각을 했다.

 

해당 문제를 풀이하기 위한 핵심 생각은 '가장 큰 번호의 게이트를 선택하는 상황이 최적이다' 라는 것이다.

단순하게 생각해도 각 비행기는 주어진 수 xi 이하의 게아트만을 선택할 수 있기에, 최대한 큰 번호의 게이트에 비행기들을 도킹시킨다면, 이후의 비행기들을 더 많이 채워넣을 수 있을 것이다.

 

이러한 논리하에 가장 큰 번호의 게이트를 선택하는 알고리즘을 구현해야 하는 것이다.

이는 각 과정당 Union 연산을 하는 분리집합으로 해결이 가능하다.

 

int Find(int x) {

    if(parent[x] == x){
        return x;
    }
    return parent[x] = Find(parent[x]);
}

분리집합에서 각 집합의 대표원소를 탐색하는 방식은 Parent[x] == x인 루트 원소를 찾을 때까지 재귀적으로 루트를 찾아나가는 형식이다.

현재 또한  주어진 범위 내에서 비어있는 게이트를 탐색해야 하는 상황이기에 정확히 들어맞는다.

 

    for(int i = 0; i < P; i++){
        int x, root;
        cin >> x;
        root = Find(x);// 최적의 게이트 탐색
        if(root == 0){
            break;
        }
        Union(root, root - 1); // greedy(현재 자리에서 선택할 수 있는 가장 큰 번호)

        ans++;

    }

 

***root는 현재 비어있는 최적의 게이트 ***

비어있는 게이트의 root원소는  자기자신이다.

이 경우에는 이 게이트를 선택한 후, 방문처리를 해주면 된다.

 

하지만 이미 비행기가 차있는 게이트에서는 자신보다 작은 게이트 중에서 큰 것 부터 탐색해 비어있는 게이트를 선택해야 한다.

 

하지만 Find와 Union 연산은 이 두가지 상황을 한줄의 코드로 처리할 수 있다.

xi에 대해서 Find연산을 하면 현재 게이트가 비어있는지의 여부와 관계없이 최적의 게이트를 반환한다.

 

더이상 자리가 없는 상황에서는 parent[0], 즉, 0을 반환하므로 break

 

비어있는 root 게이트에 비행기를 도킹하였으므로 root에 대한 정보를 초기화 한다.(더 좁은 범위에서)

Union(root, root-1) --> 이로써 대표원소가 root인 집합의 원소들은 더 작은 root값을 가리키게 된다.

 

즉, 한마디로 정리하면

각각의 원소들이 매번 최적의 게이트를 가리키도록 설계한다.

 

 

전체코드

 

#include <iostream>
using namespace std;

int parent[100001];

int Find(int x) {

    if(parent[x] == x){
        return x;
    }
    return parent[x] = Find(parent[x]);
}

void Union(int a, int b){

    a = Find(a);
    b = Find(b);
    parent[a] = b;
}

void Solve(){
    int G, P, ans = 0;

    cin >> G >> P;

    for(int i = 0; i < P; i++){
        int x, root;
        cin >> x;
        root = Find(x);// 최적의 게이트 탐색
        if(root == 0){
            break;
        }
        Union(root, root - 1); // greedy(현재 자리에서 선택할 수 있는 가장 큰 번호)

        ans++;

    }
    cout << ans;
}

int main(){
    for(int i = 0; i < 10001; i++){
        parent[i] = i;
    }
    Solve();
}