백준 10775번: 공항
공항
아이디어
기본적인 아이디어는 Greedy하게 남은 게이트 중 가장 번호가 큰 게이트에 도킹시키면 된다. 4를 입력받은 경우 4번 게이트가 남아있으면 4번, 없으면 3번, 3번도 없으면 2번.. 이런식으로 도킹하면 최대한 많이 도킹할 수 있다.
그런데 매번 입력받을 때마다 g(i)번부터 1번까지 자리가 있나 탐색을 할 수는 없는 노릇이다. 10만 * 10만이라 시간초과임. 유니온 파인드 자료구조를 통해 남은 자리가 어디인지 바로 알 수 있다!
우선 g(i)번에 도킹하는 경우 g(i)-1번과 유니온 연산을 진행한다. 숫자가 작은 쪽이 루트가 되도록 유니온 연산을 하면 된다. 이렇게 하나씩 연결하다 find(g)가 0인 경우 (즉 1번부터 g(i)번 게이트까지 꽉 찬 경우) 중단하고 답을 출력하면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
int G, P;
int p[100001];
int find(int n) {
if (p[n] < 0) return n;
return p[n] = find(p[n]);
}
void Union(int n1, int n2) {
n1 = find(n1);
n2 = find(n2);
if (n1 == n2) return;
else {
p[n2] = n1;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> G >> P;
memset(p, -1, sizeof(p));
int ans = 0;
for (int i = 0; i < P; i++) {
int g;
cin >> g;
if (find(g) == 0) break;
Union(find(g)-1, find(g));
ans++;
}
cout << ans << '\n';
return 0;
}
여담
그리디처럼 생겼는데 유니온 파인드라니..
Author And Source
이 문제에 관하여(백준 10775번: 공항), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-10775번-공항저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)