[백준] 3079번 - 입국심사

아이디어

이분탐색 문제에서 중요하다고 생각되는 점
1) 시작, 끝 점을 어떤 값으로 지정할 것 인지
2) 최솟값, 최댓값을 구하기 위한 check값을 어떻게 지정할 것인지
3) start,end 값 변경 조건

이 문제에서 start값은 문제 조건에 의해 1로 두었고, end값은 오래 걸리는 심사관한테 계속 심사받는 경우라고 생각하여 M * max(delay) 라도 두었다. 이때, delay는 심사를 하는데 걸리는 시간 리스트이다.

코드

# 입국심사
import sys
N,M = list(map(int,sys.stdin.readline().split()))
delay = [int(sys.stdin.readline().rstrip()) for _ in range(N)]

start = 1
end = M * max(delay) # 오래 걸리는 심사관한테 계속 심사받는 경우

result = 0
while(start <= end):
    check = 0
    mid = (start + end) // 2
    for d in delay:
        check += mid // d
    if check < M:
        start = mid + 1
    else:
        end = mid - 1
        result = mid
print(result)

이분 탐색은 코드가 계속 비슷한 패턴으로 작성되는 것 같다.