백준 10775 공항

10775번: 공항

문제

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

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

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

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

이러한 사고가 일어나면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

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

 

풀이

비행기는 1 ~ gi 게이트에만 도킹할 수 있으며, 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다.

만약, 도킹하고자 하는 게이트에 다른 비행기가 이미 도킹되어 있다면, 1 ~ gi-1 게이트 중에 비어있는 곳에 도킹해야 할 것이다.

gi-1, gi-2, gi-2, ... ,1 순으로 게이트가 비어있다면 그 곳에 도킹해주면 된다.

하지만 그렇게 탐색하면 시간초과가 나므로 유니온 파인드를 사용해줘야 한다.

도킹된 a게이트의 부모 노드를 a-1게이트의 부모노드로 갱신해주는 방식으로 문제를 풀면 된다. 

1. 

input

4 3 4 1 1

output

2

게이트의 개수는 4개 비행기의 개수는 3개 이고

순서대로 4, 1, 1 게이트에 도킹하려고 한다.

처음 부모 노드는 1,2,3,4 이다.

배열로 표현해서 parent[5] = { 0, 1, 2, 3, 4 } 이다.

게이트가 1부터 시작하므로 parent[0] = 0 도 만들어 주었다. 더 이상 도킹할 수 없을때 부모 노드가 0이 되게 할 것이다.

1. 비행기가 gate4에 도킹하면 다음에 4번 게이트로 오는 비행기는 3번 게이트에 도킹해야 하므로

부모 노드를 gate3의 부모노드로 바꿔준다.

2. 비행기가 gate1에 도킹한다. 다음에 1번 게이트로 오면 더이상 도킹하지못하고 공항이 폐쇄된다.

더이상 도킹하지 못하므로 gate1의 부모노드는 0이다.

3번 비행기는 gate1의 부모 노드가 0이므로 더이상 도킹할 수 없고 공항은 폐쇄된다.

최대한 도킹할 수 있는 비행기는 2개 이다.

 

2.

input

4 6 2 2 3 3 4 4

output

3

이 경우에는 게이트가 4개 비행기가 6대이다.

처음 부모 노드는 아래와 같다.

1. 2번 게이트에 도킹

2. 2번 게이트에 도킹

gate2의 부모노드는 1이고 이는 2번 게이트에는 더이상 도킹할 수 없고 1번 게이트에 도킹할 수 있음을 뜻한다.

gate2의 부모노드는 1이므로 1번 게이트에 도킹 해주고, 1번 게이트는 더이상 도킹할 수 없으므로

gate1의 부모노드는 0으로 갱신해 준다.

3. 3번 게이트에 도킹

gate3의 부모노드는 3이라서 3번 게이트에 도킹이 가능하다.

gate3의 부모노드를 gate2의 부모노드로 갱신해준다.(이 과정에서 gate2와 gate3의 부모노드는 0으로 갱신된다.)

gate3의 부모노드는 0이된다.(1~3까지는 더이상 도킹할 수 없다.)

4. 3번 게이트에 도킹

더이상 도킹할 수 없으므로 공항은 폐쇄된다.

 

최대한 도킹할 수 있는 비행기는 3대이다.

아래는 소스코드이다.

#include <iostream>
#include <vector>
 
using namespace std;
 
int getParent(vector<int> &parent,int x)
{
    if (parent[x] == x) return x;
    return parent[x] = getParent(parent, parent[x]);
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int G;    // 게이트의 수
    int P;    // 비행기의 수
    cin >> G >> P;
 
    vector<int> g;
    g.push_back(0);
    vector<int> parent;
    parent.push_back(0);
    for (int i = 0; i < P; ++i) {
        int a;
        cin >> a;
        g.push_back(a);
    }
 
    for (int i = 1; i <= G; ++i) {
        parent.push_back(i);
    }
    int cnt = 0;
    for (int i = 1; i <= P; ++i) {
        int k = getParent(parent, g[i]);
        if (k == 0) {
            break;
        }
        parent[k] = getParent(parent,k-1);
        cnt++;
    }
    cout << cnt << "\n";
    
    return 0;
}