[BOJ] 백준 10775 공항

문제 링크

www.acmicpc.net/problem/10775

10775번: 공항

 

풀이

예제 2번으로 시뮬레이션해봅시다.

 

1번 비행기)

 

 

2번 게이트가 비어 들어갈 수 있습니다.

 

2번 비행기)

 

 

2번 게이트가 비어있지 않아 그 앞의 1번 게이트로 들어갑니다.

 

3번 비행기)

 

 

3번 게이트가 비어있어 들어갈 수 있습니다.

 

4번 비행기

 

 

3번, 2번, 1번 게이트가 모두 비어있지 않아 끝나게 됩니다.

 

 

문제를 풀어봅시다.

게이트의 수가 10만이라 그냥 시뮬레이션하면 당연히 터집니다.

 

특정 게이트 번호가 주어졌을 때, 그 번호 이하의 게이트 중 가장 높은 번호를 빠르게 구할 수 있어야 합니다.

여기서 유니온-파인드를 적용하면 사용할 수 있는 게이트인지 확인하며 건너뛰는 과정을 빠르게 스킵할 수 있습니다.

 
어떤 게이트 $x$의 부모를 조회하면 현재 사용할 수 있는 $x$이하의 게이트 번호 중 가장 큰 번호가 나오게끔 구현해야 합니다.
이는 생각보다 쉽게 구현이 가능합니다.

게이트가 비어있는 초기 상태엔 자기 자신이 부모입니다. 이후 (이번에 사용한 게이트 - 1) 번을 부모로 만들어주면 됩니다.
만약 바로 앞의 게이트가 사용할 수 없는 게이트라도, 다시 그 부모를 타고 올라가면 최적의 게이트가 나오게 됩니다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;

int p[111'111], par[111'111];
int n, m;

int find(int x) {
    if (par[x] == -1) return x;
    return par[x] = find(par[x]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(par, -1, sizeof(par));
    cin >> n >> m;

    int ans = 0;
    while (m--) {
        int g;
        cin >> g;
        if ((g = find(g)) == 0) break;
        par[g] = g - 1;
        ans++;
    }
    cout << ans;
}