[백준 3079번] 파이썬 - 입국심사

백준 3079 - 입국심사

시간 제한 1초, 메모리 제한 128MB

# 조건

• 상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다.
• 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다.
• k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.
• 가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다.
• 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다.
• 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다.
• 하지만 항상 이동을 해야 하는 것은 아니다.
• 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 된다.
• 상근이와 친구들은 모두 컴퓨터 공학과 학생이기 때문에, 어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될지 궁금해졌다.
  • 예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 7초와 10초라고 하자.
  • 줄에 서 있는 사람이 6명이라면, 가장 첫 두 사람은 즉시 심사를 받으러 가게 된다. 7초가 되었을 때, 첫 번째 심사대는 비어있게 되고, 세 번째 사람이 그곳으로 이동해서 심사를 받으면 된다.
  • 10초가 되는 순간, 네 번째 사람이 이곳으로 이동해서 심사를 받으면 되고, 14초가 되었을 때는 다섯 번째 사람이 첫 번째 심사대로 이동해서 심사를 받으면 된다.
  • 20초가 되었을 때, 두 번째 심사대가 비어있게 된다.
  • 하지만, 여섯 번째 사람이 그 곳으로 이동하지 않고, 1초를 더 기다린 다음에 첫 번째 심사대로 이동해서 심사를 받으면, 모든 사람이 심사를 받는데 걸리는 시간이 28초가 된다.
  • 만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다.
• 상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 N과 M이 주어진다. (1<=N<=100,000, 1<=M<=1,000,000,000)
• 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다.(1<=Tk<=10^9)

출력

• 첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력한다.

# 접근 방법

• 한 심사대 당 최대 10억의 시간이 소요되므로 브루트 포스로는 풀 수 없다.
• 이분 탐색을 이용한다면 제한 시간 내에 문제를 해결할 수 있다.
  • left = 최소 시간
  • right = 최대로 걸리는 시간 = (시작) 가장 긴 시간의 심사대 * 인원수
• while 문 내부
  • total = 현재 mid 시간으로 모든 심사대에서 받을 수 있는 총 인원 수
  • mid => m명이 심사를 모두 받는 시간
• 즉, 현재의 mid 값으로 모든 심사대를 순회했을 때 total 값이 K보다 크다면 right = mid - 1로, 반대의 경우라면 left = mid + 1로 변경하며 적절한 값을 찾아나간다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

N, K = map(int, input().split())
time = []
for _ in range(N):
    time.append(int(input()))

left = min(time)
right = max(time) * K
result = float('inf')

while left <= right:
    mid = (left + right) // 2
    total = 0

    for i in time:
        total += mid // i

    if total >= K:
        right = mid - 1
        result = min(result, mid)

    else:
        left = mid + 1
print(result)