[BOJ] 10775. 공항

이정진·2022년 7월 18일
0

PS

목록 보기
64/76
post-thumbnail

공항

알고리즘 구분 : 자료 구조, 그리디 알고리즘, 분리 집합

문제

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력
첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력
승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

예제 입력 1
4
3
4
1
1
예제 출력 1
2
예제 입력 2
4
6
2
2
3
3
4
4
예제 출력 2
3
힌트
예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다.

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

문제 풀이

이 문제는 옛날에 풀다가 포기하고, 오늘 오랜만에 다시 도전했는데 결국 질문 게시판의 도움에 힘입어서 풀었다.

문제에서 비행기가 들어오는 순서대로 게이트를 채워가는 과정이라고 명시하였기에, 비행기가 들어올 때 들어갈 수 있는 게이트 중에서 그리디하게 선택해야 한다는 과정까지 파악하였다. 그렇기에, 비행기별 게이트 범위가 주어질 때, 해당 게이트 범위 번호를 배열에서 증가시키면서 게이트 번호보다 들어올려는 비행기 수가 증가하게 될 경우, break하는 과정으로 로직을 짜려고 했다.

Ex)
int gate[100001];

memset(gate, 0, sizeof(gate));

for(int i = 0; i < p; i++) {
	int input;
    cin >> input;
    
    if(gate[input] < input) {
    	gate[input]++;
    }
    else {
    	break;
    }
    
}

위의 로직은 예제 1번은 답이 나오지만, 2번 예제는 답이 제대로 나오지 않는다.
2번 예제로 본다면, 첫 두 비행기에 의해 1, 2번 게이트가 차게 되는데, 그렇다면 3번째 비행기가 입력되었을 때는 gate[3]의 값이 3이 되어야 한다. 즉, 게이트 번호를 입력받을 때마다, 그 번호 뒤의 모든 게이트 배열의 값을 업데이트 해주어야 하는데, 이는 게이트의 범위가 10^5이기에 무조건 TLE가 나오는 상황이 되버린다는 것이다.

새로 로직을 짜려고 하는 과정에서, 게이트의 범위 입력받은 상황에서, 현재 들어갈 수 있는 게이트 중 가장 큰 번호를 가진 게이트에 들어가는 것이 최댓값을 도출해낼 수 있다는 것을 알고 있었지만, 어떻게 구현해야 할지는 파악하지 못하고 있었다. 그 과정에서, 질문 게시판을 통해 해당 과정을 분리집합, 즉 유니온-파인드를 통하여 구현할 수 있음을 깨닫고 해당 방법으로 로직을 구현하게 되었다. 예를 들어, 현재 비행기가 3번 게이트를 들어가고 싶다고 한다면, 해당 게이트가 차있는지 여부를 확인하고, 차있다면 2번 게이트를 들어갈 수 있는지, 안된다면 1번 게이트를 들어갈 수 있는지 이렇게 순차적으로 확인하는 과정이 되는 것인데, 이를 부모 노드의 연결을 통해서 해결할 수 있다. 즉, 3번 게이트의 부모노드가 자기 자신이라면, 2번 게이트로 unionParent를 하여 추후 다시 3번 게이트 범위의 비행기가 들어오게 된다면, 자연스럽게 2번 게이트로 연결해주는 과정을 거치도록 하는 것이다. 자세한 방식은 아래 소스 코드를 통해 확인하면 된다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

int g, p;
vector<int> node;
int parent[100001];
int findParent(int parent[], int x);
void unionParent(int parent[], int a, int b);
int solve();


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> g >> p;
    // parent 배열 초기화
    for(int i = 1; i < g + 1; i++) {
        parent[i] = i;
    }

    for(int i = 0; i < p; i++) {
        int input;
        cin >> input;
        node.push_back(input);
    }

    cout << solve() << endl;

    return 0;
}

int findParent(int parent[], int x) {
    if(parent[x] != x) {
        return parent[x] = findParent(parent, parent[x]);
    }

    return parent[x];
}

void unionParent(int parent[], int a, int b) {
    int pa = findParent(parent, a);
    int pb = findParent(parent, b);

    if(pa < pb) {
        parent[pb] = pa;
    }
    else {
        parent[pa] = pb;
    }
}

int solve() {
    int result = 0;

    for(auto now : node) {
        int nowP = findParent(parent, now);

        if(nowP == 0) {
            return result;
        }
        else {
            unionParent(parent, nowP, nowP - 1);
            result++;
        }
    }

    return result;
}

0개의 댓글