[C++] 백준 온라인 저지 10775번 공항 풀이

공항에 도킹할 수 있는 최대 비행기 수를 구하는 문제

 

---

문제

 

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

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

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

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

 

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 10^5)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 10^5)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

 

 

풀이

 

 여러 입력이 주어질 때 가능한 범위 내에서 가장 높은 번호에 도킹해야 최대한 많은 비행기를 도킹할 수 있기 때문에 입력으로 주어지는 숫자부터 1씩 줄여나가면서 거꾸로 탐색해야 합니다. 

 

 처음엔 단순 그리디로

if (가능한 게이트 중 가장 높은 숫자가 비어 있다면)

-> 거기에 도킹

else (비어 있지 않다면)

-> 한 칸씩 앞으로 이동하면서 도킹 가능한 곳을 확인하는 과정을 1번 게이트를 만날 때 까지 반복한다. (while (1 < 게이트번호))

-> 1번까지 갔는데도 비어있지 않으면 도킹 불가능한 것이고 이후 입력도 받지 않는다. 

 

 이렇게 짰으나 else 문의 도킹 가능한 게이트를 확인하는 과정에서 아무 예외처리를 해 주지 않았기 때문에 1번까지 이미 꽉 차 있는데도 의미없는 탐색을 하는 코드를 짰었습니다. 그래서 입력이 커지니까 저기에서 시간 초과가 났습니다. 그 후로 암만 최적화를 해도 시간 초과를 피하질 못 해서... 구글링을 하였습니다. 

 

https://mapocodingpark.blogspot.com/2020/06/10775.html

백준 10775번 공항

 

 최적화에 참고한 블로그

 

 이 풀이의 핵심은 다음에 도킹해야 할 위치를 기록해서 탐색 횟수를 줄여주는 것입니다. 각 게이트 번호에 이 게이트를 사용하고 나면 다음에 사용해야 할 게이트 번호를 기록해 주어서 다음 입력이 들어왔을 때엔 각 게이트에 저장된 다음 게이트 번호로 바로 이동해서 그 게이트가 사용 가능한지 아닌지(0번을 만나는지 만나지 않는지) 확인해서 도킹을 하거나 중단하는 것입니다. 

 

 

코드

 

#include <iostream>
#include <vector>

using namespace std;

int nextPos = 0;
vector<int> gates;

int GetPos(int cur)
{
    //현재 게이트가 -1이라면 아직 사용하지 않은 곳임
    //해당 게이트 번호를 리턴한다.
    if (0 > gates[cur])
        return cur;
    
    //-1보다 크다면 사용한 곳이다.
    //현재 게이트 다음에 사용해야 할 번호를 리턴한다.
    return gates[cur] = GetPos(gates[cur]);
}

bool isAble(int cur)
{
    //도킹할 위치를 찾는다.
    int pos = GetPos(cur);
    //0번이면 도킹 불가능 함
    if (0 == pos)
        return false;
    
    //현재 게이트에 다음에 사용해야 할 번호를 저장한다.
    gates[pos] = GetPos(pos - 1);
    return true;
}

int main()
{
    int G, P;
    cin >> G >> P;
    
    int answer = 0;
    //게이트들의 초기값은 -1로 설정
    gates.assign(G + 1, -1);
    for (int i = 1; P >= i; i++)
    {
        int input;
        cin >> input;
        
        //해당 위치에 도킹이 가능한지 확인한다.
        if (isAble(input))
            answer++;
        else
            break;
    }
    
    cout << answer;
    
    return 0;
}