Boj10775 공항
문제 방향을 잡는데 시간이 오래 걸렸다. set으로 문제를 풀땐, timeOut 이 났다. 왜 났을까? 원인을 모르겠따…
gi 가 주어진다면, 되도록 gi 에 도킹하고 도킹할수 없다면 gi-1 에 도킹하는 식으로 문제를 접근하였다. 도킹이 가능하다면, (도킹한 게이트 -1)와 union을 해준다.
gi게이트에 다음 비행기가 접근할 시, 사용 가능한 게이트를 부모로 두게 해두었다.
#include<iostream>
using namespace std;
int g, p, num, idx = 1, ans = 0, arr[100100];
int find(int num) {
if (num == arr[num]) return num;
return arr[num] = find(arr[num]);
}
int main() {
scanf("%d %d", &g, &p);
for (int i = 0; i <= g; i++) {
arr[i] = i;
}
ans = p;
for (int i = 0; i < p; i++) {
scanf("%d", &num);
int bn2 = find(arr[num]);
if (bn2 == 0) { ans = i; break; }
arr[num] = bn2-1;
}
printf("%d", ans);
}