k루피 예산으로 구매 가능한 초콜릿의 최대 개수 찾기 - C++ 프로그램

n개의 요소를 가진 배열 A와 세 값 l, r, k가 주어진다고 가정해 보겠습니다. Amal은 초콜릿을 구매하고 싶지만, 너무 비싼 초콜릿도 너무 저렴한 초콜릿도 사지 않으려 합니다. 가게에는 n개의 서로 다른 초콜릿 바가 있으며, 각각의 가격은 배열 A에 담겨 있습니다. 가격이 r보다 크면 '너무 비싼' 것이고, l보다 작으면 '너무 저렴한' 것으로 간주합니다. 또한 그는 최대 k루피까지만 지출할 수 있습니다. 이때 Amal이 구매할 수 있는 초콜릿의 최대 개수를 구하는 것이 우리의 과제입니다.

예를 들어 입력이 A = [1, 2, 3, 4, 5, 6], l = 3, r = 5, k = 10이라면 출력은 2가 됩니다. 가격이 3루피와 4루피인 초콜릿 두 개를 합계 7루피에 구매할 수 있기 때문입니다.

문제 해결 접근 방식

이 문제는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 가장 저렴한 초콜릿부터 우선적으로 구매해야 같은 예산으로 더 많은 개수를 살 수 있습니다.
• 따라서 배열을 오름차순으로 정렬한 뒤, 가격이 허용 범위 [l, r] 안에 있는 초콜릿을 순서대로 구매합니다.
• 남은 예산보다 비싼 초콜릿을 만나면 더 이상 구매가 불가능하므로 반복을 종료합니다.

알고리즘 단계

다음 단계를 따라 문제를 해결합니다.

n := 배열 A의 크기
ans := 0
배열 A를 오름차순으로 정렬
i := 0으로 초기화하고, i < n인 동안 i를 1씩 증가시키며 반복:
    만약 A[i] > k이면:
        반복문 탈출
    만약 l <= A[i] <= r이면:
        k := k - A[i]
        ans를 1 증가
ans 반환

C++ 구현 예제

더 나은 이해를 돕기 위해 전체 구현 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A, int l, int r, int k) {
    int n = A.size();
    int ans = 0;
    sort(A.begin(), A.end());
    for (int i = 0; i < n; ++i) {
        if (A[i] > k)
            break;
        if (A[i] >= l && A[i] <= r) {
            k -= A[i];
            ++ans;
        }
    }
    return ans;
}
int main() {
    vector<int> A = { 1, 2, 3, 4, 5, 6 };
    int l = 3;
    int r = 5;
    int k = 10;
    cout << solve(A, l, r, k) << endl;
}

입력

{ 1, 2, 3, 4, 5, 6 }, 3, 5, 10

출력

2

복잡도 분석

정렬에 O(n log n)의 시간이 소요되며, 이후 배열을 한 번만 순회하므로 전체 시간 복잡도는 O(n log n)입니다. 추가 공간은 정렬에 필요한 공간 외에는 상수 수준이므로 공간 복잡도는 O(1)입니다.