[백준][python]3079 입국심사

문제

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

소스코드 

import sys
input = sys.stdin.readline
if __name__ == "__main__":
    n,m = map(int,input().split())
    time = [int(input()) for _ in range(n)]
	#time.sort() 정렬하지 않아도 정답
    l = min(time)
    r = max(time) * m 

    res = r
    

    while l <= r:
        target = 0
        mid = (l + r) // 2 

        for t in time:
            target +=  mid // t
            if target >= m :
                break

        if target >= m :
            res = min (res,mid)
            r = mid -1
        else :
            l = mid + 1
            
    print(res)

 

설명

입국심사대의 갯수와 각 소요시간이 주어졌을 때 가장 빠르게 모든 대기인원이 입국 심사를 끝내는 방법을 구해야한다.

 

처음에 (소요시간 * 인원 수)를 배열에 넣고 정렬하는 방식으로 그리디로 풀었다가 시간초과와 메모리 초과를 당했다. 문제 조건에 소요 시간의 최대값이 10**9 이기 때문에 당연한 결과 ㅠ.ㅠ

 

그렇기 때문에 이분탐색으로 가장 짧은 시간에 모든 인원을 체크할 수 있는 시간을 구해야 한다.

 

- 이분탐색에서 중요한 점은 왼쪽값, 오른쪽값, 타겟 값을 정하는 것이다.

왼쪽 값: 가장 빠른 시작 시간 ->  min (time) 

오른쪽 값: 가장 오래된 끝나는 시간  -> max(time) * m (가장 긴 시간 * 모든 인원수 )

타겟 값: 입국심사를 받은 사람 수

 

타겟 값이 내가 원하는 값이 나왔어도 최대한으로 시간을 줄여야 하기 때문에 종료하지 않고 최소값을 계속 체크해줘야한다.

target 이 내가 원하는 값보다 크다 -> 더 많은 사람을 체크할 수 있다 -> 시간이 넉넉하다 -> 최소값이 아니다.