C++로 정확히 K개의 잔을 채우는 데 필요한 최소 병 개수 구하기

문제 설명

물이 담긴 N개의 잔과 각 잔의 용량 목록이 주어집니다. 이때 정확히 K개의 잔을 채우기 위해 필요한 최소 병 개수를 구하는 것이 과제입니다. 각 병의 용량은 100단위입니다.

예시

N = 5, K = 4, capacity[] = {1, 2, 3, 2, 1}인 경우를 살펴보겠습니다.

• 용량이 가장 작은 4개의 잔은 {1, 1, 2, 2}이며, 이를 모두 채우는 데 필요한 물의 양은 총 6단위입니다.
• 병 하나의 용량이 100단위이므로, 병 1개만 열면 충분합니다.

알고리즘

• 정확히 K개의 잔을 채우려면 용량이 가장 작은 K개의 잔을 선택해야 합니다.
• 필요한 병의 총 개수는 다음과 같이 계산할 수 있습니다.

필요한 병 수 = ⌈ (용량이 가장 작은 K개 잔의 용량 합) ÷ (병 1개의 용량) ⌉

즉, 선택된 잔들의 용량 합을 병 용량으로 나눈 뒤 올림(ceil) 처리하면 됩니다.

구현 예제

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int minBottles(int *capacity, int n, int k) {
    // 오름차순 정렬하여 가장 작은 용량의 잔들을 앞쪽에 배치
    sort(capacity, capacity + n);
    int sum = 0;
    // 가장 작은 용량의 K개 잔의 합계 계산
    for (int i = 0; i < k; ++i) {
        sum += capacity[i];
    }
    // 병 용량(100)으로 나눈 후 올림 처리
    return ceil((double)sum / 100);
}
int main() {
    int capacity[] = {1, 2, 3, 2, 1};
    cout << "필요한 최소 병 개수 = " << minBottles(capacity, 5, 4) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

필요한 최소 병 개수 = 1

동작 원리 요약

1. 잔의 용량 배열을 오름차순으로 정렬합니다.
2. 정렬된 배열에서 가장 작은 K개의 용량을 더합니다.
3. 합계를 병 용량(100)으로 나누고 올림하여 최소 병 개수를 구합니다.

이 접근 방식의 시간 복잡도는 정렬 단계가 지배적이므로 O(N log N)입니다.