백준 10775번 공항[C++]

1. 문제 풀이

gi가 주어졌을 때 1번부터 gi 중 아직 도킹하지 않은 게이트를 찾는 쿼리를 최적화하는 것이 중요한 문제 같습니다. 배열 p의 값을 p[x] = x를 가지게 한 다음 유니온 파인드의 경로 압축을 응용하여 도킹할 게이트를 찾게 하여 최적화하였습니다. p[x] = x인 값을 찾으면 아직 도킹하지 않은 게이트 번호입니다. 도킹을 시도한 다음 p[x]를 1 감소하여 p[x]를 x-1로 갱신해 p[x-1]에서 게이트 번호를 찾게끔 구현하였습니다. 이 때 찾은 번호가 0이면 더 이상 도킹이 불가능하다는 base condition도 추가하였습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n, m;

vi idx(100005);

int find_gate(int x){
  if(x == 0 || idx[x] == x) return x;
  return idx[x] = find_gate(idx[x]);
}

int main() {
  fastio(nullptr, false);
  
  // init
  iota(all(idx), 0);

  // input
  cin >> n >> m;

  // solve
  int ans{};
  while(m--){
    int gate;
    cin >> gate;
    gate = find_gate(gate);
    if(!gate) break;
    idx[gate]--;
    ans++;
  }
  
  // output
  cout << ans;
}