[BOJ] 10775: 공항

[BOJ] 10775: 공항

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

비행기를 최대한 많이 도킹하기 위해서는, 도킹 가능한 곳 중 가장 큰 번호의 게이트에 도킹해야 한다.

빈 곳을 매번 찾게 되면, O(G*P)로 문제를 시간 안에 해결하지 못한다.

아이디어가 떠오르지 않아서 타 블로그에서 아이디어를 얻었다. union-find를 쓰는게 핵심이었다.

p[i] = 입력 i가 들어왔을 때, 도킹 가능한 게이트의 최댓값, 0일 경우 도킹 불가

문제를 해결하는데는 지장 없지만, 최상단 노드를 부모로 지정하는 경로 압축을 사용하면 시간 복잡도를 줄일 수 있다.

(O(N) -> O(1))

#include #include using namespace std; int p[100001]; int find(int x) { if (p[x] == x) return x; return p[x] = find(p[x]); } int main() { int G, P, ans = 0; scanf("%d %d", &G;, &P;); for (int i = 1; i <= G; i++) p[i] = i; for (int i = 0; i < P; i++) { int a; scanf("%d", &a;); // 경로 압축 int tmp = p[a] = find(a); if (!tmp) break; ans++; p[tmp] = tmp - 1; } printf("%d", ans); }

union-find 어어어엄청 오랜만에 본다... 문제를 많이 풀어보면서 자료구조나 풀이방법을 다양하게 익혀야 적용 가능할 것 같다.

memset 참고(https://torbjorn.tistory.com/297)

from http://gokong.tistory.com/21 by ccl(A) rewrite - 2021-10-07 18:00:42