Koko Eating Bananas

질문 하나로 시작해 보세요. 바나나가 p개 있는 더미를 속도 k로 먹는 데 얼마나 걸릴까요? 코코는 한 시간에 k개를 먹고 같은 시간 안에는 다른 더미로 옮겨 가지 않으므로, 더미 하나를 먹는 데는 올림한 p / k시간이 걸립니다. 속도가 4일 때 바나나가 10개인 더미는 3시간이 걸립니다. 4개, 4개를 먹고 나서 2개를 먹은 뒤 쉬는 식입니다. 모든 더미에 걸리는 시간을 더하고 그 합계를 h와 비교하세요.

이제 속도를 1, 2, 3 순서로 시도해 보고, 합계가 h 이내인 첫 번째 속도를 반환하세요. 더 느린 속도는 모두 시도했지만 조건을 만족하지 못했으므로, 이렇게 하면 가장 작은 속도가 됩니다. 반복문은 항상 멈춥니다. 가장 큰 더미의 크기와 같은 속도라면 각 더미를 한 시간씩 먹으면 되고, h는 더미 개수 이상이기 때문입니다.

문제는 반복문이 얼마나 오래 실행될 수 있느냐입니다. 바나나가 거의 10^9개씩 들어 있는 더미가 5000개이고 h = 5000이라면, 답은 10^9에 가까우므로 반복문은 약 10억 번 실행되고 각 확인 작업은 더미 5000개를 모두 읽습니다. 총 약 5 × 10^12단계입니다. 여기서 m은 가장 큰 더미의 크기입니다.

1부터 가장 큰 더미까지의 모든 속도를 “이 속도라면 제시간에 끝낼 수 있는가?”라는 질문에 대한 답의 행으로 생각해 보세요. 속도가 빨라질수록 각 더미를 처리하는 데 걸리는 시간은 같거나 줄어드므로, 전체 시간은 줄어들 수밖에 없습니다. 따라서 답의 행은 아니요, 아니요, 아니요, 그리고 답부터는 예로 이어지며, 다시 아니요로 돌아가지 않습니다. 찾으려는 것은 첫 번째 예이고, 아니요와 예로 이루어진 정렬된 행은 바로 이진 탐색으로 절반씩 나누는 대상입니다.

항상 답을 포함하는 lo부터 hi까지의 범위를 유지하세요. 범위는 1부터 가장 큰 더미로 시작합니다. 가장 큰 더미의 속도는 더미마다 한 시간이 걸리고 h는 이를 감당할 수 있으므로, 이 범위는 안전합니다. 중간 속도 mid를 확인하세요. 시간 안에 끝낼 수 있다면 답은 mid이거나 그보다 느린 속도이므로 hi = mid로 설정하고 mid를 범위에 남겨 둡니다. 시간 안에 끝낼 수 없다면 더 느린 모든 속도도 실패하므로 lo = mid + 1로 설정합니다. lo와 hi가 같아지면 그 속도가 답입니다.

첫 번째 예시를 따라가 보세요. 더미는 4, 10, 7, 3이고 h = 6입니다. 범위는 1부터 10입니다. 속도 5에서는 1 + 2 + 2 + 1 = 6시간이 걸려 조건을 만족하므로 범위는 1부터 5가 됩니다. 속도 3에서는 2 + 4 + 3 + 1 = 10시간이 걸려 너무 오래 걸리므로 범위는 4부터 5가 됩니다. 속도 4에서는 1 + 3 + 2 + 1 = 7시간이 걸려 여전히 너무 오래 걸리므로 범위는 5부터 5가 되고, 답은 5입니다.

각 확인마다 범위가 절반으로 줄어드므로, 최대 10^9개의 속도가 있는 범위도 약 30번 확인하면 됩니다. 확인당 더미가 5000개라면 약 150000단계로 끝나며, 수조 단계가 필요한 것과 비교하면 훨씬 적습니다.