[백준 / BOJ] C++ 10775 공항

10775번: 공항

 

문제

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

10775번: 공항

 

 

풀이

개인적으로 지문 이해가 어려운 문제였다. 각 비행기는 g번 이하의 숫자의 게이트에 도킹이 가능하고 이미 도킹이 되어있는 곳에는 도킹할 수 없다. 비행기가 도킹을 할 수 없다면 공항은 폐쇄된다. 최대한 많은 비행기를 도킹할 때 가능한 도킹 수를 출력하는 문제다.

 

유니온 파인드 알고리즘을 사용해서 풀었다. 처음에 비행기가 g번 이하의 게이트에 도킹해야 한다면 g번 게이트에 도킹시킨 후, g번 게이트와 g-1번 게이트를 union 한다. 그러면 이후 g번 이하 게이트에 도킹해야 할 때 find 함수를 통해 g가 가리키는 곳을 확인하면. g-1번을 가리키게 되어 비어있는 게이트에 도킹할 수 있게 된다.

 

만약 위 과정을 반복하다가 0번과 union 하게 되는 경우, 더 이상 0과 같은 컴포넌트에 속한 게이트는 그 번호 이하의 빈 게이트가 없다는 것을 뜻하게 된다. 따라서 입력받은 g를 find 했을 때 0이 return 된다면 공항은 폐쇄되어야 한다.

 

 

코드

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

vector<int> p;

int find(int x) {
  if (p[x] != x)
    p[x] = find(p[x]);
  return p[x];
}

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if (x < y)
    p[y] = x;
  else
    p[x] = y;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int G, P, ans = 0;
  cin >> G >> P;
  p.resize(G + 1);
  iota(p.begin(), p.end(), 0);
  while (P--) {
    int g;
    cin >> g;
    int x = find(g);
    if (x == 0) {
      break;
    } else {
      ans++;
      merge(x, x - 1);
    }
  }
  cout << ans;
  return 0;
}