N개의 바나나 더미가 있고, i번째 더미에는 piles[i]개의 바나나가 놓여 있습니다. 경비원들은 현재 자리를 비운 상태이며 H시간 후에 돌아올 예정입니다. 코코는 시간당 바나나를 먹는 속도 K를 직접 결정할 수 있습니다.
매시간 코코는 한 개의 더미를 선택해 그 더미에서 K개의 바나나를 먹습니다. 만약 해당 더미에 남은 바나나가 K개보다 적다면, 남은 바나나를 모두 먹고 그 시간 동안에는 더 이상 다른 더미를 먹지 않습니다.
코코는 되도록 천천히 먹고 싶어 하지만, 동시에 경비원이 돌아오기 전까지 모든 바나나를 먹어야 한다는 조건이 있습니다. 따라서 우리가 구해야 하는 것은 H시간 안에 모든 바나나를 먹을 수 있는 최소 정수 K입니다.
예를 들어 입력이 [3,6,7,11]이고 H = 8이라면, 출력은 4가 됩니다.
해결 접근 방법
이 문제는 이진 탐색(Binary Search)을 활용하면 효율적으로 해결할 수 있습니다. 먹는 속도 K의 가능한 범위는 1부터 가장 큰 더미의 바나나 개수까지이며, 이 범위 안에서 조건을 만족하는 최솟값을 찾으면 됩니다.
1단계: 검증 함수 ok() 정의
배열 a와 두 값 x(후보 속도), h(주어진 시간)를 인자로 받는
ok()메서드를 정의합니다.time := 0으로 초기화합니다.
i를 0부터 배열 a의 크기까지 반복하면서:
time := time + a[i] / x (각 더미를 먹는 데 필요한 시간)
a[i] mod x가 0이 아니라면(나머지가 존재하면) time에 1을 추가합니다. 나머지 바나나를 먹는 데 추가로 1시간이 필요하기 때문입니다.
time <= h이면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
2단계: 이진 탐색으로 최소 속도 찾기
n := piles 배열의 크기, sum := 0, low := 1, high := 0으로 초기화합니다.
i를 0부터 n-1까지 반복하면서 high를 max(piles[i], high)로 갱신합니다. 즉, high는 가장 큰 더미의 바나나 개수가 됩니다.
low < high인 동안 다음을 반복합니다:
mid := low + (high − low) / 2
ok(piles, mid, H)가 true라면 high := mid로 설정하고, false라면 low := mid + 1로 설정합니다.
반복이 끝나면 high를 반환합니다. 이것이 조건을 만족하는 최소 속도 K입니다.
핵심 아이디어는 속도 K가 커질수록 필요한 총 시간은 줄어든다는 점입니다. 따라서 '속도 → 필요 시간' 관계가 단조 감소하므로, 이진 탐색으로 경계값을 빠르게 좁혀 나갈 수 있습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
bool ok(vector <int>& a, int x, int H){
int time = 0;
for(int i = 0; i < a.size(); i++){
time += a[i] / x;
time += (a[i] % x ? 1 : 0);
}
return time <= H;
}
int minEatingSpeed(vector<int>& piles, int H) {
int n = piles.size();
lli low = 1;
lli sum = 0;
lli high = 0;
for(int i = 0; i < n; i++)high = max((lli)piles[i], high);
while(low < high){
int mid = low + (high - low) / 2;
if(ok(piles, mid, H)){
high = mid;
}else{
low = mid + 1;
}
}
return high;
}
};
main(){
vector<int> v = {3,6,7,11};
Solution ob;
cout << (ob.minEatingSpeed(v, 8));
}입력
[3,6,7,11] 8
출력
4
동작 원리 검증
입력 [3,6,7,11], H = 8일 때 속도 K = 4를 적용해 보면:
더미 3개 → 1시간 (3 ÷ 4 = 0, 나머지 있음)
더미 6개 → 2시간 (6 ÷ 4 = 1, 나머지 있음)
더미 7개 → 2시간 (7 ÷ 4 = 1, 나머지 있음)
더미 11개 → 3시간 (11 ÷ 4 = 2, 나머지 있음)
총 8시간이 소요되어 조건을 정확히 만족합니다. 속도를 3으로 낮추면 총 10시간이 걸려 조건을 벗어나므로, 정답은 4가 됩니다.
이 알고리즘의 시간 복잡도는 O(n × log(max(piles)))로, 각 이진 탐색 단계마다 배열 전체를 순회하는 ok() 함수가 호출되기 때문입니다. 완전 탐색(O(n × max(piles)))에 비해 훨씬 효율적입니다.