baekjoon 10775:공항

baekjoon 10775 공항

10775번 공항

접근

문제 크기게 굉장히 크기 때문에 일단 dp는 될 수 없다고 생각했다.
처음엔 1번째 gate부터 넣고 더 여유있는 비행기들이 뒤로 옮기는 방식으로 했다.
왜 처음부터 가장 자기가 갈 수 있는 최대로 안갔냐고 묻는다면 어짜피 거기서도 많이 차면 아래로 한칸씩 내려와야한다고 생각했다.
하지만 이렇게는 결국 O(n^2)밖에 되지 않았다. 1초안에 풀려면 최소 O(nlogn)은 되야 했다.
그래서 찾아보니 2가지 방법이 있었다.
각 칸에 몇칸 뛰어 넘어야하는지 적으면서 하는 방법이 있었고
또하나는 union-find로 같이 있는 비행기들을 한 묶음으로 만들고 그들이 모두 그다음 빈칸을 가리키도록 하는 방법이다.
사실 그냥 union-find를 쓰면 이것도 다 돌기 때문에 O(n^2)이지만 union-find에 path compression을 적용하여 모두 다 root node로 직접연결 시켜버렸다.
이렇게 되면 빈칸 찾는데 걸리는 시간이 가장 빠르면 O(1), 평균 O(logn)으로 충분히 빠르게 찾을 수 있게 된다.

시간 초과 된 코드

#include <iostream>
#include <vector>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int g, p; cin >> g >> p;
  vector<pair<int, int>> gates(g);
  for(auto& i: gates){
    i.first = i.second = -1;
  }
  int ans = 0;
  for(int i = 0; i < p; i++){
    int a; cin >> a;
    pair<int, int> curr = {i, a-1};
    bool inserted = false;
    for(int j = 0; j < g; j++){
      if(gates[j].first == -1 && curr.second >= j){
        gates[j] = curr;
        inserted = true;
        ans++;
        break;
      }
      else{
        if(gates[j].second > curr.second && curr.second >= j){
          pair<int, int> temp = gates[j];
          gates[j] = curr;
          curr = temp;
          continue;
        }
      }
    }
    if(!inserted){
      cout << ans;
      return 0;
    }
  }
  cout << ans;
  return 0;
}

성공 코드1

#include <iostream>
#include <vector>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int g, p; cin >> g >> p;
  vector<pair<int, int>> gates(g);
  vector<int> gatesClever(g);
  for(auto& i: gates){
    i.first = i.second = -1;
  }
  int ans = 0;
  for(int i = 0; i < p; i++){
    int a; cin >> a;
    pair<int, int> curr = {i, a-1};
    int j = a-1;  
    while(gatesClever[j] > 0 && j>=0){
      int temp = gatesClever[j];
      gatesClever[j]++;
      j -= temp;
    }
    if(j < 0){
      cout << ans;
      return 0;
    }
    gates[j] = curr;
    gatesClever[j]++;
    ans++;
  }
  cout << ans;
  return 0;
}

성공 코드2

#include <iostream>
#include <vector>
using namespace std;
int find(int x, vector<int>& gatesUf){
  if(gatesUf[x] == x) return x;
  return gatesUf[x] = find(gatesUf[x], gatesUf);
}
bool merge(int a, int b, vector<int>& gatesUf){
  a = find(a, gatesUf);
  b = find(b, gatesUf);
  if(a == b) return false;
  gatesUf[b] = a;
  return true;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int g, p; cin >> g >> p;
  vector<bool> gates(g+1);
  vector<int> gatesUf(g+1);
  for(int i = 0; i < g+1; i++) gatesUf[i] = i;
  int ans = 0;
  for(int i = 0; i < p; i++){
    int a; cin >> a; 
    int t = find(a, gatesUf);
    if(t == 0){
      cout << ans;
      return 0;
    }
    gates[t] = true;
    ans++;
    merge(t-1, t, gatesUf);
  }
  cout << ans;
  return 0;
}

배운 점

union-find에 대해 응용도 해보았고, union-find가 분리 집합을 만드는 알고리즘 중 하나라는 것을 알게 되었다.
union-find의 구현도 여러가지 방법이 있다는 것을 알게 되었다.