[백준] 10775 - 공항

1. 문제

10775번: 공항

2. 개요

G개의 게이트가 있는 공항이 있다.

이곳에 P대의 비행기가 도착할 예정이다.

i번째 비행기를 1이상 gi이하의 게이트에 영구적으로 도킹할 예정이다.

어떤 비행기가 도킹할 수 없어진다면 공항이 폐쇄된다.

이 때, 최대 도킹 가능한 비행기의 대수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

각 비행기들의 gi이하의 게이트 중 비어있는 최대 번호의 게이트에 비행기를 넣으면 된다.

그런데 비행기, 게이트 각각 100000이라 반복문을 이용한 완전탐색으로 풀면 시간초과가 걸린다.

함수를 이용한 재귀로 최대번호를 찾아내는 방법을 이용하면 된다.

3-2. Python

import sys

G = int(sys.stdin.readline())

gates = [0 for i in range(G + 1)]
dests = [i for i in range(G + 1)]
answer = 0

P = int(sys.stdin.readline())

def uni(num):
    if dests[num] == num:
        return num

    dests[num] = uni(dests[num])
    return dests[num]

isover = False
for i in range(P):
    goal = int(sys.stdin.readline())

    if isover == False:
        docloc = uni(goal)

        if docloc == 0:
            isover = True
            continue
        
        gates[docloc] += 1
        answer += 1

        dests[docloc] = uni(dests[docloc - 1])

print(answer)

3-3. C#

namespace boj_10775
{
    internal class Program
    {
        static int[] dests;

        static void Main(string[] args)
        {
            int answer = 0;
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            int G = int.Parse(sr.ReadLine());

            dests = new int[G + 1];

            for (int i = 0; i < G + 1; i++) { dests[i] = i; }
            
            int P = int.Parse(sr.ReadLine());

            bool isover = false;
            for (int i = 0; i < P; i++)
            {
                int goal = int.Parse(sr.ReadLine());

                if (!isover)
                {
                    int docloc = uni(goal);

                    if (docloc == 0)
                    {
                        isover = true;
                        continue;
                    }

                    answer++;
                    dests[docloc] = uni(docloc - 1);
                }
            }
            Console.WriteLine(answer);
        }

        static int uni(int num)
        {
            if (dests[num] == num)
                return num;

            dests[num] = uni(dests[num]);
            return dests[num];
        }
    }
}