[백준 3079] 입국심사 Python

📘 문제 정보

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

 

📝 문제 해석

• 입국심사대가 여러 개 있으며, 각 심사대는 한 명의 사람을 처리하는 데 걸리는 시간이 서로 다르다.
  총 M명의 사람이 심사를 받기 위해 줄을 서 있으며, 각 사람은 빈 심사대에 들어가게 된다.
  • 사람 수 M: 최대 1,000,000,000명
  • 심사대 수 N: 최대 100,000개
  • 각 심사대 시간 T: 최대 1,000,000,000
  → 시간 범위가 매우 크기 때문에 단순 탐색이 아닌 이분 탐색을 사용해야 한다.

 

💡 풀이 아이디어

🔑 핵심 접근: 이분 탐색 대상은 '시간'

• 최소 시간 start = 0, 최대 시간 end = 10^18로 설정 (심사 시간 최대가 10^9, 사람 수도 10^9라서 최대는 10^9 * 10^9 = 10^18까지 가능)
• 이분 탐색의 mid 시간에 대해
  • 각 심사대가 그 시간 동안 몇 명을 처리할 수 있는지 계산
  • 총 인원 수가 목표 m명 이상이면 시간 줄이고
  • 부족하면 시간 늘리는 방식으로 이분 탐색 수행

 

✅ 핵심 전략

1. start = 0, end = 10^18, answer = INF
2. 이분 탐색 진행
   • mid 시간 동안 심사 가능한 총 인원 계산
   • count >= m이면 answer 갱신 후 end = mid - 1
   • 아니면 start = mid + 1
3. 최종적으로 answer에 가장 빠르게 모든 사람을 심사할 수 있는 최소 시간이 저장됨

# pypy3

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [int(input()) for _ in range(n)]

INF = 10**18
start, end = 0, INF
answer = INF
while start <= end:
    mid = (start+end)//2
    count = 0
    for i in range(len(arr)):
        count += mid//arr[i]

    if count >= m:
        end = mid-1
        answer = min(answer, mid)
    else:
        start = mid+1

print(answer)