문제 설명
크기가 N인 배열이 주어지며, 각 인덱스는 하나의 바구니(bucket)를 나타내고 해당 위치에는 배달해야 할 항목들이 담겨 있습니다. 모든 항목을 K번의 이동(tour) 안에 배달해야 하며, 한 번의 이동에서는 오직 하나의 바구니에서만 항목을 꺼낼 수 있습니다. 이때 목표는 모든 항목을 K번의 이동 안에 배달하기 위해 한 번의 이동당 최소 몇 개의 항목을 배송해야 하는지 구하는 것입니다.
예시
항목이 {1, 3, 5, 7, 9}개씩 담긴 5개의 바구니와 10번의 이동 기회가 주어졌다고 가정해 보겠습니다. 한 번에 3개씩 배달하면 다음과 같습니다.
- 1번째 바구니(항목 1개): 필요한 이동 횟수 = 1
- 2번째 바구니(항목 3개): 필요한 이동 횟수 = 1
- 3번째 바구니(항목 5개): 필요한 이동 횟수 = 2 (3개 + 2개)
- 4번째 바구니(항목 7개): 필요한 이동 횟수 = 3 (3개 + 3개 + 1개)
- 5번째 바구니(항목 9개): 필요한 이동 횟수 = 3 (3개 + 3개 + 3개)
총 이동 횟수는 10번으로 주어진 K와 정확히 일치합니다. 따라서 이 경우의 정답은 3입니다.
접근 방법 (알고리즘)
- 한 번의 배달당 나눠 담을 항목 수의 후보값을 정합니다.
- 1부터 가장 큰 바구니의 항목 수까지 차례대로 시도하면서, 각 후보값에 대해 모든 바구니를 배달하는 데 필요한 총 이동 횟수를 계산합니다.
- 총 이동 횟수가 K 이하가 되는 첫 번째 후보값이 곧 요구되는 최소 배달 항목 수입니다.
각 바구니에 필요한 이동 횟수는 ceil(바구니 크기 ÷ 후보값), 즉 올림 나눗셈으로 구할 수 있습니다. 후보값을 작은 수부터 순서대로 검사하므로, 조건을 처음으로 만족하는 값이 자연스럽게 최솟값이 됩니다.
C++ 구현 예제
#include <iostream>
#include <climits>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
// 한 번의 이동당 i개씩 옮길 때 필요한 총 이동 횟수를 계산
int minItemsDelivered(int *arr, int n, int k) {
int maxElement = INT_MIN;
for (int i = 0; i < n; ++i) {
maxElement = max(maxElement, arr[i]);
}
// 후보값을 1부터 최대 항목 수까지 하나씩 시도
for (int i = 1; i <= maxElement; ++i) {
int tours = 0;
for (int j = 0; j < n; ++j) {
if (arr[j] % i == 0) {
tours += arr[j] / i;
} else {
tours += arr[j] / i + 1; // 나머지가 있으면 올림 처리
}
}
if (tours <= k) {
return i; // 조건을 만족하는 첫 번째(최소) 값 반환
}
}
return 1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int k = 10;
cout << "배달해야 할 최소 항목 수 = "
<< minItemsDelivered(arr, SIZE(arr), k) << endl;
return 0;
}실행 결과
위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.
배달해야 할 최소 항목 수 = 3
복잡도 분석
각 후보값마다 배열 전체를 순회하므로 시간 복잡도는 O(N × M)입니다. 여기서 M은 가장 큰 바구니에 담긴 항목 수입니다. 항목 수가 매우 큰 경우에는 가능한 답의 범위(1 ~ M)에서 이분 탐색(binary search)을 적용하면 O(N × log M)으로 성능을 크게 개선할 수 있습니다.