백준 10775 - 공항

문제 설명

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

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

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 1~g사이 게이트에만 도킹할 수 있는 P개의 비행기가 순서대로 주어졌을 때 최대 몇 개까지 도킹할 수 있는지 구하면 된다.

 

첫 번째 시도했던 방법은 게이트의 상태를 비트셋으로 표현하여 bfs를 진행했다.

G = 5 일 때, 00000부터 11111까지 표현하도록 한 것이다.

P개의 비행기의 도킹 가능 영역을 queue에 넣으면서 진행했는데 메모리 초과가 발생했다.

 

두 번째로 생각한 방법은 비행기가 도킹할 수 있는 게이트 중 가장 큰 곳에 도킹하는 것이 최적해를 보장한다는 생각으로 그리디를 진행했다.

하지만, 이번엔 시간 초과가 발생했다. $O(N^2)$의 연산이 필요하기 때문이다.

 

최적화를 고려해야 했다.

내가 생각한 방법은 도킹가능한 게이트를 일렬로 나열한 후, 각 비행기가 이진 탐색을 통해 자신이 도킹할 가장 큰 게이트를 찾도록 했다.

도킹할 게이트가 존재한다면 해당 게이트를 배열에서 지워주고 이 과정을 반복했다.

for (int i = 0; i < P; i++)
{
    if (gates.size() == 0)
    {
        cout << i;
        return 0;
    }

    int g;
    cin >> g;

    int pos = lower_bound(gates.begin(), gates.end(), g) - gates.begin();
    if (pos >= gates.size()) pos = gates.size() - 1;
    if (gates[pos] > g) pos--;

    if(pos < 0)
    {
        cout << i;
        return 0;
    }

    gates.erase(gates.begin() + pos);
}

 

해당 방법으로도 충분히 AC를 받을 수 있었다.

하지만, 다른 풀이의 시간이 짧아 방법을 확인해 보니 유니온-파인드를 통해 도킹된 게이트 집합을 관리하는 방식을 사용했다.

현재 비행기를 게이트에 도킹을 시키며 도킹된 게이트는 1칸 앞에 있는 게이트를 선두로 지정하며 게이트의 집합을 만들어 나가는 방식이다.

https://www.acmicpc.net/source/93051790

 

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int G, P;
vector<int> gates;

int main() 
{
    INPUT_OPTIMIZE;

    cin >> G >> P;

    for (int i = 1; i <= G; i++)
    {
        gates.push_back(i);
    }

    for (int i = 0; i < P; i++)
    {
        if (gates.size() == 0)
        {
            cout << i;
            return 0;
        }

        int g;
        cin >> g;

        int pos = lower_bound(gates.begin(), gates.end(), g) - gates.begin();
        if (pos >= gates.size()) pos = gates.size() - 1;
        if (gates[pos] > g) pos--;

        if(pos < 0)
        {
            cout << i;
            return 0;
        }

        gates.erase(gates.begin() + pos);
    }

    cout << P;

    return 0;
}

---