(10775) 공항

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

단계별로 풀어보기

42단계(그리디 알고리즘 2) 2번째

 

 

 

비행기가 착륙 가능한 게이트는 1~g(i)번이므로 낮은 번호의 게이트는 가능한 비행기가 많은 반면 높은 번호의 게이트로 갈수록 적어진다. 따라서 어떤 비행기가 도착했을 때 착륙 가능한 게이트 중 가장 높은 번호의 게이트에 보내는 것이 이득이다.

그런데 N이 10만이므로 이 값을 for문으로 찾으면 O(N^2)이라 시간초과가 난다.

x번 게이트에 비행기가 들어갔다면, 다음에 x번이나 x-1번으로 오는 비행기는 x-1로 안내해야 한다. 따라서 유니온 파인드를 쓸 수 있다. 만약 x-1번에도 비행기가 들어갔다면 x-2, x-1, x번 전부 같은 집합으로 묶이고 이 중 어느 게이트로 가려든 비행기든 x-2번에 들어설 수 있다.

집합의 결과가 0이라면 1번 게이트에 비행기가 들어가 더 이상 남은 게이트가 없다는 의미이므로 그 순간 비행기의 수가 최대값이다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int uf[100'001];

int find(int x){
  if(uf[x]==x)  return x;
  else  return uf[x]= find(uf[x]);
}

void merge(int x, int y){
  x= find(x);
  y= find(y);

  if(x==y)  return;

  uf[y]= x;
  return;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int g, p, u, ans;

  cin >> g >> p;
  
  vector<int> uf(g+1);
  
  for(int i=1;i<=g;i++)  uf[i]= i;
  
  auto find= [&](auto self, int x) -> int {
    if(uf[x]==x)  return x;
    else  return uf[x]= self(self, uf[x]);
  };
  
  auto merge= [&](int x, int y){
    x= find(find, x);
    y= find(find, y);
    
    uf[y]= x;
  };
  
  for(ans=0;ans<p;ans++){
    int x;
    
    cin >> x;
    
    x= find(find, x);
    
    if(!x)  break;
    else  merge(x-1, x);
  }

  cout << ans;
  
  return 0;
}