티스토리 뷰
https://www.acmicpc.net/problem/10775
처음에는 세그먼트 트리를 이용하여 풀어 보기 위해 많은 시간 고민했지만 쉽지 않았습니다.
결국은 태그에서 힌트를 얻어 유니온 파인드를 이용하여 문제를 해결했습니다.
- 필요한 배경지식
유니온 파인드 : Union-Find (Disjoint-set)
- 문제 해결 방법
g가 주어질때 들어갈 수 있는 가장 큰 번호의 게이트에 비행기를 도킹해 주면 비행기를 최대로 도킹할 수 있습니다.
이처럼 그리디하게 도킹하는 과정에서 유니온 파인드를 이용하면 문제를 해결할 수 있습니다.
아래와 같은 입력을 예시로 생각해 봅시다.
G = 7, P = 7 |
g[i] : 7 3 3 3 1 5 6 |
(도킹한 게이트는 괄호로 표현)
1번째 비행기 도착 --> 1 2 3 4 5 6 (7)
2번째 비행기 도착 --> 1 2 (3) 4 5 6 (7)
3번째 비행기 도착 --> 1 (2 3) 4 5 6 (7)
4번째 비행기 도착 --> (1 2 3) 4 5 6 (7)
1,2번째 비행기가 도착했을때 해당되는 게이트는 비어있으므로 도킹해 줍니다.
3번째 비행기 도착에서 3번 게이트에는 이미 도킹된 비행기가 있으므로 도킹할 수 있는 가장 큰 번호의 게이트에 도킹해 주어야 합니다. 그렇다면 2번 게이트에 도킹할 수 있습니다.
4번째 비행기 도착에서도 3번 게이트에 이미 도킹된 비행기가 존재합니다. 이 경우 도킹된 집합 (2 3)보다 작은 번호의 게이트 중 가장 큰 번호의 게이트가 1이므로 1번 게이트에 도킹할 수 있고 집합 (1 2 3)으로 표현할 수 있습니다.
5번째 비행기의 g는 1이고, (1 2 3) 4 5 6 (7) 의 도킹상태에서는 집합(1 2 3)보다 작은 0번 게이트가 있어야 하지만 0번 게이트는 존재하지 않으므로 4를 답으로 출력할 수 있습니다.
아래의 코드에서는 각 집합의 부모를 도킹되어야 할 게이트로 설정했습니다.
즉, g가 입력으로 들어오면 g의 부모가 다음으로 도킹되어야 할 게이트의 번호이고 그 번호는 g보다 작거나 같으면서 도킹이 안된 게이트이므로 merge( par, par-1 )로 집합처리 할 수 있습니다. (par = g의 부모 = 도킹할 게이트)
이때 par가 0이라면 도킹할 게이트가 없음을 의미하므로 결과를 출력해주면 됩니다.
- C++ 전체 코드
#include<bits/stdc++.h>
using namespace std;
int G,P;
int parent[100001]{};
int find(int k) {
if (k == parent[k]) return k;
else return parent[k] = find(parent[k]);
}
void merge(int a, int b) {
a = find(a);
b = find(b);
parent[a] = b;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>G>>P;
// 부모를 자기 자신으로 초기화
for(int i=1; i<=G; i++) parent[i] = i;
int g, ans = 0;
while(P--){
cin>>g;
int par = find(g); // g의 부모 = 다음으로 도킹할 게이트 번호
if (par != 0) {
merge(par, par-1); // merge함수에서 집합의 부모는 par-1로 설정됨
ans++;
}
// 집합의 부모가 0 -> 도킹되어야 할 게이트가 0
else break; // 0번 게이트는 존재하지 않으므로 break
}
cout<<ans;
}
'알고리즘 공부 > 문제풀이' 카테고리의 다른 글
백준 1368번 - 물대기 (0) | 2021.05.22 |
---|---|
백준 2512번 - 예산 (0) | 2021.05.21 |
백준 16345번 - 인구 이동 (0) | 2021.05.20 |
백준 14891번 - 톱니바퀴 (0) | 2021.05.20 |
백준 21277번 - 짠돌이 호석 (0) | 2021.05.18 |