SWEA 3074. 입국심사(python)

SWEA 문제 3074. 입국심사

문제의 저작권은 SW Expert Academy에 있습니다.
문제링크(SWEA)
문제링크(프로그래머스)

문제설명

M명의 사람이 입국심사를 받으려고 한다.

입국심사대에서는 한 줄 서기를 시행하고 있다.

심사대는 총 N개가 있어서 1번에서 N번 까지의 번호가 붙어있다.

k번 심사대에서 입국심사관이 심사를 하는 데 걸리는 시간은 tk이고 심사가 끝나면 지연 없이 다음 사람을 심사할 수 있다.

처음 모든 심사대는 비어 있고 심사를 할 준비가 되어 있다.

한 심사대에서는 한 명의 사람만 심사할 수 있으며, 사람들은 비어 있는 심사대가 있으면 바로 가서 심사를 받을 수 있다고 하자.

이 사람들이 모두 심사를 받기 위해 걸리는 최소한의 시간을 구하는 프로그램을 작성하라.

예를 들어 6명의 사람이 심사를 받기 위해 서있고, 두 심사대가 있고 각각 심사를 위해 걸리는 시간이 7초, 10초라고 하자.

가장 첫 두 사람은 즉시 심사를 받게 된다.

7초가 되면 첫 번째 심사대는 비어있게 되고, 세 번째 사람이 즉시 그곳으로 이동해서 심사를 받게 된다.

다음으로 10초가 되면 두 번째 심사대가 비어있게 되고, 네 번째 사람이 즉시 그곳으로 이동해서 심사를 받게 된다.

이런 식으로 28초가 되면 6명의 사람이 모두 심사가 끝난다.

입출력 예

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

솔루션

1. 총 소요된 시간의 하한, 상한 값을 조정하는 이진탐색으로 구현
2. 총 소요된 시간 내 각 심사위원이 맡은 사람의 수의 합이 M보다 크거나 같으면 조건을 충족하므로 이보다 작은 값이 있는지 상한값을 줄여 찾아본다.
3. 총 소요된 시간 내 각 심사위원이 맡은 사람의 수의 합이 M보다 작다면 조건을 충족할 만큼 시간이 크지 않으므로 하한 값을 높여 충족하는지 확인한다.
   
   

코드

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

#테스트케이스 입력
T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    time_lst = []
    for _ in range(N):
        time_lst.append(int(input()))
    #하한, 상한 초기화
    left, right = 1, max(time_lst)*M
    result = 0
    while left <= right:
        mid = (left + right)//2
        people = 0
        # 총 소요된 시간에서 각 심사위원이 맡은 사람의 수의 합이 M을 넘어야한다.
        # while문이 끝나고나면 조건을 충족하는 시간 중 가장 작은 값이 결과 값으로 저장된다.
        for t in time_lst:
            people += mid//t
            # M을 넘는다면 조건을 충족하는 시간으로 result에 저장하고 상한 값을 낮춘다.
            if people >= M:
                result = mid
                right = mid -1
                break
        # M을 넘지 못한다면 시간의 값이 커져야하므로 하한 값을 높인다.
        if people < M:
            left = mid + 1
    print('#{} {}'.format(tc, result))