티스토리 뷰

반응형

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

 

10775번: 공항

예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불

www.acmicpc.net

처음에는 세그먼트 트리를 이용하여 풀어 보기 위해 많은 시간 고민했지만 쉽지 않았습니다.

결국은 태그에서 힌트를 얻어 유니온 파인드를 이용하여 문제를 해결했습니다.

 

 

  • 필요한 배경지식

유니온 파인드 : 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
댓글
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/01   »
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
글 보관함