10775번: 공항
예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불
www.acmicpc.net
도킹하려는 게이트 번호인 x가 주어지면
union-find의 find를 이용하여 1 ~ x의 게이트 중 사용 가능한 게이트의 가장 큰 번호를 찾습니다.
찾은 번호인 p가 1 ~ x에 있으면 비행기를 도킹시켜주면 되고, parent[p] = p - 1로 바꿔줍니다.
p가 0이면 1 ~ x의 게이트 모두 사용이 불가능하므로 break를 하고 갯수를 출력해줍니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <iostream>
using namespace std;
int parent[100001], list[100001];
int N, M, ans;
int find(int v) {
if (parent[v] == v) return v;
return parent[v] = find(parent[v]);
}
void func() {
for (int i = 0; i < M; i++) {
int x = list[i];
int p = find(x);
if (!p) break;
parent[p] = p - 1;
ans++;
}
cout << ans << '\n';
}
void init() {
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
}
void input() {
cin >> N >> M;
for (int i = 0; i < M; i++) {
cin >> list[i];
}
init();
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > Union-Find' 카테고리의 다른 글
| boj 20040 사이클 게임 (0) | 2021.06.27 |
|---|---|
| boj 1043 거짓말 (0) | 2021.04.05 |
| boj 4195 친구 네트워크 (0) | 2021.03.17 |
| boj 1976 여행 가자 (0) | 2021.03.17 |
| boj 1717 집합의 표현 (0) | 2021.02.06 |