백준 3079번: 입국심사

백준 3079번: 입국심사

한참을 헤매다가 결국 못 풀어서 다른 분들의 답을 보고 풀 수 있었다.

import sys
input= sys.stdin.readline
N,M = map(int,input().split())
time = list(int(input()) for _ in range(N))
start, end = min(time), max(time)*M
ans = end
while start<=end:
    total = 0
    mid = (start+end)//2
    for i in range(N):
        total += mid//time[i]
    if total>=M:
        end = mid -1
        ans = min(mid,ans)
    else:
        start = mid +1

print(ans)

이분탐색문제는 항상 코드를 짜는 것 자체보다는 뭘 기준으로 탐색을 하고, 최솟값과 최대값의 초기값을 뭘로 할지를 찾는게 어렵다. 그리고 이게 이분탐색문제라는 말을 안 들었으면 이분탐색 문제라는 걸 알아채기도 좀 어려운 것 같다. 정렬가능한 범위 내에서 탐색을 필요로 하며 입,출력값의 범위가 매우 커서 완탐은 힘든 문제, 혹은 상한값/하한값을 기준으로 값을 조정하는 문제면 이분탐색을 고려해볼 것. 이분 탐색 구현 참고 게시글
나는 처음에 start, end를 0, max(time)*M으로 했다가 그 이후 풀이가 잘 안 떠올라서 time 배열을 sort한 후에 0, N으로 잡고 헀는데, 생각해보니 중간에 기다렸다가 줄을 서기도 할 수 있어 정해진 시간 값의 조합만으로 이분탐색을 하면 안 되는 거 였다. total값을 기준으로 탐색하는 것까지는 생각을 했는데 start, end값 설정을 잘못해서 틀렸다. 이분탐색 문제를 좀 더 많이 풀어봐야겠다고 생각했다..