[파이썬/Python] 백준 3079번: 입국심사

숨·2024년 8월 16일

📌 문제 탐색하기

N : 입국심사대 수 $(1 ≤ N ≤ 100,000)$
M : 인원 수 $(1 ≤ M ≤ 1,000,000,000)$
T : k번 심사대의 심사 소요 시간 $(1 ≤ T_{k} ≤ 10^9)$

문제 풀이

⭐️ 심사 진행 과정

초기 : 모든 심사대 비어있음

한 심사대 → 한 번에 1명의 사람만 가능

가장 앞의 사람

비어있는 심사대 보이면 거기로 가서 심사 👌

대기 시간 짧은 심사대로 가서 심사 👌

위와 같이 심사를 진행했을 때 걸리는 시간의 최솟값을 구하는 문제이다.

N, M의 범위가 매우 크기 때문에 시간복잡도를 최대한 줄일 수 있는 방법을 사용해야 한다.

1️⃣ 찾고자 하는 변수를 심사에 걸리는 시간이라고 정의하고, 이 시간이 M의 사람들을 모두 심사하는데 충분한 시간인지 확인하면서 적절한 값을 찾으면 될 것이다.
→ 이를 이분탐색을 통해 찾아본다❗️

⭐️ 충분한 시간인지 확인하는 방법

해당 시간 내에 M명 심사 가능한지 확인

계산 방법
* 각 심사대마다 몇 명의 사람을 처리할 수 있는지 계산

해당 시간을 각 처리 시간으로 나눈 몫을 누적

누적값이 M보다 큰지 작은 여부를 확인

2️⃣ 위 방법을 이분 탐색으로 구현하기 위해 시작점, 끝점을 정의한다.

심사에 걸리는 시간 T, N, M 모두 최솟값이 1이다.
→ 시작점 1로 잡는다❗️
T, N, M의 최댓값을 기준으로 끝점을 정의한다면?
→ $T_{k} = 10^9$ , $N = 10^5$ , $M = 10^9$ 이므로 for문으로 각 시간에 접근해서 연산한다면 시간 초과가 일어날 것 같다.
심사대 시간 중 최댓값을 모든 사람이 이용한다면 현재 상황에서 가장 큰 값을 얻게 될 것 같다.
→ 끝점으로 잡는다❗️

가능한 시간복잡도

while문으로 이분탐색 → $O(log(end - start))$
for문으로 사람 수 연산 → $O(N)$

최종 시간복잡도
총 $O(N * log(max(T) * M))$ 이 된다.
최악의 경우 $O(10^5 * log(10^9 * 10^9)$ 이므로
이는 1초 내에 연산이 가능하다.

알고리즘 선택

이분 탐색으로 심사에 걸리는 시간 탐색

이분 탐색 구현

1️⃣ 시작값을 1, 마지막값을 max(T) * M로 지정하고 중앙값을 심사에 걸리는 시간로 정의한다.
2️⃣ 시작값이 마지막값과 같아지거나 더 작아질 때까지 탐색을 지속한다.
3️⃣ 정답 저장할 변수, 심사 완료 사람 저장할 변수를 정의한다.
4️⃣ 심사 완료된 사람의 수 누적합을 계산하면서 해당 시간이 적절한지 확인한다.
5️⃣ 심사 완료 사람 수 < M라면? → 시작값을 mid+1로 변경해 시간 증가
6️⃣ 심사 완료 사람 수 >= M라면? → 현재 값을 정답으로 갱신하고 마지막값을 mid-1로 변경해 시간 감소
7️⃣ 이분 탐색이 종료될 때까지 탐색을 지속한다.

📌 코드 설계하기

N, M 입력
N번 반복해 T 입력
이분 탐색 초기값 선언
이분 탐색 구현
결과 출력

📌 시도 회차 수정 사항

1회차

범위의 최댓값을 이분 탐색의 조건과 동일한 방식으로 구하려고 했다.
심사 시간의 최댓값을 각 시간으로 나누어 심사받은 사람의 누적합으로 설정하면 되지 않을까라고 생각했는데 그건 사람 수에 대한 누적합이지 시간에 대한 값은 아니었다. 정의한 내용을 헷갈리는 바람에 범위를 잘못 지정했다.

2회차

예제 입력1의 출력이 60이 나왔다.
이분 탐색 내 조건을 반대로 써서 발생한 일이었다.

📌 정답 코드

import sys

input = sys.stdin.readline

# N, M 입력
N, M = map(int, input().split())

# N번 반복해 T 입력
T = [int(input()) for _ in range(N)]

# 이분 탐색 초기값 정의
start = 1
end = max(T) * M

# 정답을 최댓값으로 초기화
answer = end

# 이분 탐색 구현
while start <= end:
    mid = (start + end) // 2
    # 심사한 사람 누적합 저장 변수
    count = 0

    # 각 시간에 대한 사람 수 누적합 계산
    for t in T:
        count += mid // t

    # 처리 가능한 사람 수가 M보다 작으면 시간을 늘려야 한다
    if count < M:
        start = mid + 1

    # 처리 가능한 사람 수가 M보다 크면 정답을 갱신하고 시간을 줄여본다
    else:
        answer = mid
        end = mid - 1

# 정답 출력
print(answer)