[BOJ] 10775 - 공항

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

BOJ - 공항

문제 유형: 분리 집합, 그리디

문제 난이도: Gold II

시간 제한: 1초

메모리 제한: 256MB

 

문제

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

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

공항에는 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~x라면, 그 비행기는 최대한 범위 내에서 가장 큰 번호로 가는 것이 반드시 유리하다. 더 작은 숫자의 비행기의 자리를 위해 양보하는 것이 최선의 해를 구하는 것이기 때문이다.

그럼, 어떻게 현재 범위에서 유효한 남은 자리를 찾을까? 우선순위 큐를 떠올릴 수 있겠지만, 뺐다가 다시 넣는 시간을 생각하면 비효율적임을 알 수 있다.

대신, 분리 집합을 이용한다. parent[x] = x로 초기화시켜서, 현재 x기준 이용할 수 있는 가장 큰 게이트의 번호가 x라는 의미이다.

그리고, 사용된다면, 이전 번호로 넘겨야 한다. 즉, x-1로 parent를 바꾼다.

경로 압축을 이용하여 다음에 사용할 번호를 빠르게 불러올 수 있음을 알 수 있다.

만약 다음의 번호가 0이라면, 더 이상 도킹이 불가능하다는 의미이다.

 

코드

C++

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

int getRoot(int x, vector<int> &parent) {
  if (parent[x] == x) {
    return x;
  }
  return parent[x] = getRoot(parent[x], parent);
}

bool dockPlane(int targetCell, vector<int> &parent) {
  int root = getRoot(targetCell, parent);
  if (root == 0)
    return false;
  parent[root] = root - 1;
  return true;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int g, p;
  cin >> g >> p;
  vector<int> planes(p);
  for (int i = 0; i < p; ++i) {
    cin >> planes[i];
  }

  vector<int> parent(g + 1);
  iota(parent.begin(), parent.end(), 0);

  int ans = 0;
  for (const auto &plane : planes) {
    if (!dockPlane(plane, parent))
      break;
    ans++;
  }

  cout << ans << "\n";

  return 0;
}