[백준] 10775 공항

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

1번부터 g번째 게이트 중 하나에 도킹할 수 있으므로, g게이트부터 1번까지 도킹이 가능하다면 바로 도킹을 시도해야합니다.

 만약 g 게이트가 이미 도킹하여 사용중이라면 g 보다 작은 수 중 도킹이 가능한 가장 큰 수를 찾아야합니다.

해당 수를 찾기위해 게이트가 도킹이 되면, 다음으로 도킹이 가능한 게이트 번호를 가리키도록 하였습니다.

2) 알고리즘

• 그리디

3) 풀이 코드

사용 언어 - Python

import sys
sys.setrecursionlimit(100000000)
sys.stdin = open('input.txt')


def union(a: int) -> int:
    '''
    게이트에 비행기 도킹

        params:
            a: 도킹 시도하려는 게이트 번호
        returns:
            a: 도킹한 게이트 번호
    '''
    a = find(a)
    li[a] = a - 1
    return a


def find(a: int) -> int:
    '''
    해당 게이트보다 작은 게이트에서 도킹이 가능한 게이트를 찾기 위해 탐색
    도킹이 가능한 게이트 번호 반환

        params:
            a: 도킹 가능 여부 확인이 필요한 게이트 번호
        returns:
            a: 도킹 가능한 게이트 번호
    '''
    if li[a] != a and a >= 0:
        li[a] = find(li[a])
        return li[a]
    return a


def solution() -> int:
    '''
    비행기가 들어오는 순서에 따라 도킹 시뮬레이션

        returns:
            ans: 도킹 가능한 최대 비행기 수
    '''
    ans = 0

    for _ in range(P):
        num = int(sys.stdin.readline())

        if union(num-1) == -1:  # 도킹한 게이트 번호가 -1이면, 불가능한 게이트이므로 종료
            break
        else:                   # 도킹 성공시 정답 1 증가
            ans += 1

    return ans


# 입력 값
G = int(sys.stdin.readline())
P = int(sys.stdin.readline())

# 도킹할 게이트들 목록
li = list(range(G))

print(solution())

---

🔗 문제 링크

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

10775번: 공항

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다