[백준 10775] 공항 (C#, C++) - soo:bak

문제 링크

10775번 - 공항

설명

비행기마다 도킹할 수 있는 게이트 번호의 상한이 주어지고, 한 번 사용한 게이트는 다시 쓸 수 없습니다. 도킹이 불가능해지면 그 이후 비행기는 모두 거절됩니다. 최대 몇 대의 비행기를 도킹할 수 있는지 구하는 문제입니다.

접근법

각 비행기에 대해 가능한 게이트 중 가장 큰 번호를 선택하는 것이 최적입니다. 예를 들어 게이트가 4개이고 상한이 3인 비행기가 왔을 때, 1번이나 2번 대신 3번에 도킹해야 합니다. 작은 번호를 먼저 사용하면 이후 상한이 1이나 2인 비행기가 도킹할 자리가 없어질 수 있기 때문입니다.

사용 가능한 가장 큰 게이트를 빠르게 찾기 위해 유니온 파인드를 사용합니다. 처음에는 각 게이트가 자기 자신을 가리킵니다. 게이트를 사용하면 그 게이트를 바로 왼쪽 게이트에 연결합니다. 예를 들어 3번 게이트를 사용하면 3번의 부모를 2번으로 설정합니다.

이후 상한이 3인 비행기가 또 오면 3번에서 찾기 연산을 수행합니다. 3번의 부모가 2번이므로 2번을 찾게 되고, 2번이 아직 사용 가능하면 그곳에 도킹합니다. 2번을 사용하면 다시 2번의 부모를 1번으로 연결합니다. 이렇게 연결이 계속 이어지다가 결국 0번에 도달하면 더 이상 도킹할 게이트가 없다는 의미입니다.

찾은 게이트 번호가 0이면 종료하고, 그때까지 도킹한 비행기 수가 답입니다.

Code

C#

using System;

namespace Solution {
  class Program {
    static int[] parent = Array.Empty<int>();

    static int Find(int x) {
      if (parent[x] == x)
        return x;
      parent[x] = Find(parent[x]);
      return parent[x];
    }

    static void Union(int a, int b) {
      a = Find(a);
      b = Find(b);
      parent[a] = b;
    }

    static void Main(string[] args) {
      var G = int.Parse(Console.ReadLine()!);
      var P = int.Parse(Console.ReadLine()!);
      parent = new int[G + 1];
      for (var i = 0; i <= G; i++)
        parent[i] = i;

      var docked = 0;
      for (var i = 0; i < P; i++) {
        var g = int.Parse(Console.ReadLine()!);
        var root = Find(g);
        if (root == 0)
          break;
        docked++;
        Union(root, root - 1);
      }
      Console.WriteLine(docked);
    }
  }
}

C++

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

typedef vector<int> vi;

vi parent;

int Find(int x) {
  if (parent[x] == x)
    return x;
  return parent[x] = Find(parent[x]);
}

void Union(int a, int b) {
  a = Find(a);
  b = Find(b);
  parent[a] = b;
}

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

  int G, P; cin >> G >> P;
  parent.resize(G + 1);
  for (int i = 0; i <= G; i++)
    parent[i] = i;

  int docked = 0;
  for (int i = 0; i < P; i++) {
    int g; cin >> g;
    int root = Find(g);
    if (root == 0)
      break;
    docked++;
    Union(root, root - 1);
  }

  cout << docked << "\n";

  return 0;
}