공항 10775

문제

접근 방법

공항에 비행기를 최대한 많이 집어넣는 것이 목적이다.
하지만 1부터 g까지의 게이트에만 도킹할 수 있기에 잘 생각하고 도킹해야 한다.

1부터 g라는 범위가 존재하기에 앞에서부터 채워나가는 것보단 뒤에서부터 채워나가는 것이 좋다.
그래야 앞자리 숫자가 오더라도 막힘없이 집어넣을 수 있다.
그렇기에 무조건 뒤에서부터 1씩 줄여가면서 넣는 것이 이득이라는 것을 알 수 있다.

그렇다면 이미 사용한 경우를 하나씩 확인하면서 1씩 줄여나가기만 하면 될까?
비행기와 게이트가 10^5의 범위를 가지고 있는 것을 알 수 있다.
10^5의 게이트가 10^5의 게이트 범위를 갖는 비행기를 갖는다면 10^10의 해당하는 연산을 해야 할 것이다.

이러한 연산을 줄여주려면 거슬러 오르는 연산을 줄여줘야 한다.
거슬러 오르는 과정을 저장하여 사용해 주면 해당하는 연산을 줄여줄 수 있다.

코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> parent;
int G, P, g, cnt;
int find(int cur)
{
    if (parent[cur])
        return parent[cur] = find(parent[cur] - 1);
    else
    {
        if (cur == 0)
            return 0;
        return parent[cur] = cur;
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> G >> P;
    parent = vector<int>(G + 1);
    while (P--)
    {
        cin >> g;
        if (find(g))
            ++cnt;
        else
            break;
    }
    cout << cnt;
    return 0;
}

풀이

거슬러 오르는 과정은 유니온 파인드를 응용하여 부모에 저장하는 방식으로 해결하면 된다.