백준 10775번 공항

🔒[문제 url]

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

🔑알고리즘

비행기가 도착한 순서대로 도킹해야하므로, $g_i$ 이하의 수들 중 가장 큰 번호 게이트에 도킹해야한다. 즉, Greedy하게 도킹한다.

또한, $g_i$부터 시작하여 1씩 감소해가며 도킹할 게이트를 정하게 된다.
따라서, $g_i$에 도킹을 했다면 $g_i-1$가 부모 게이트인 집합을 만들어 도킹할 게이트를 빠르게 찾게끔 하자. Union-Find

• 예시INPUT : 7 5 4 3 5 1 4를 통해 살펴보자.
  • 초기 상태에서 게이트의 부모는 자기 자신(1) (2) (3) (4) (5) (6) (7)이다.
  • 첫 비행기인 4가 도착하면, 집합은 (1) (2) (3 4) (5) (6) (7)와같이 형성된다.
  • 3 도착시 집합은 (1) (2 3 4) (5) (6) (7)이다.
  • 5 도착시 집합은 (1) (2 3 4 5) (6) (7)이다.
  • 1 도착시 집합은 (0 1) (2 3 4 5) (6) (7)이다.
  • 4 도착시, 도킹할 게이트인 0은 존재하지 않으므로 출력은 4가 된다.

🐾부분 코드

int Find(int x)
{
    if (parent[x] == x) return x;
    else return parent[x] = Find(parent[x]);
}

void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
    parent[x] = y;
}

<Union-Find 구현>

// Union Find Init
for (int i = 1; i <= g; i++) parent[i] = i;

<집합 초기화>
초기 상황에서, 각 게이트의 부모 게이트는 자기 자신이다.

for (int i = 1; i <= p; i++)
{
    int G = Find(gi[i]);
    // No gate to dock.
    if (!G) break;

    // There's gate to docking
    ans++;
    Union(G, G - 1);
}

<도킹 구현>
각 비행기가 도킹하고자 하는 게이트가 속한 집합의 부모 게이트를 찾아 도킹한다.
이때, 부모 게이트가 0인 경우 공항은 폐쇠된다.
도킹을 $g_i$에 정상적으로 한 경우, $g_i-1$을 집합의 부모 게이트로 추가하여 갱신한다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
using namespace std;

int g, p;
int gi[100001];
int parent[100001];

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> g >> p;
    for (int i = 1; i <= p; i++) cin >> gi[i];
}

int Find(int x)
{
    if (parent[x] == x) return x;
    else return parent[x] = Find(parent[x]);
}

void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
    parent[x] = y;
}

void SOLVE()
{

    // Union Find Init
    for (int i = 1; i <= g; i++) parent[i] = i;

    int ans = 0;

    for (int i = 1; i <= p; i++)
    {
        int G = Find(gi[i]);
        // No gate to dock.
        if (!G) break;

        // There's gate to docking
        ans++;
        Union(G, G - 1);
    }

    cout << ans;
}



int main()
{
    INPUT();

    SOLVE();

}

🥇문제 후기

Union-Find를 생각하지 않고 이중for문으로 풀면서 끽해야 골5겠네~ 하였으나 시간초과에 뺨맞은 문제. 과연 코테 현장에서 최적화를 생각할 여유가 있을까..? 라고 생각했으나.. 여유가 생길때까지 공부하면 되지!