문제 소개
어떤 상점에서 여러 종류의 상품을 판매하고 있다고 가정해 보겠습니다. 각 상품에는 고유한 가격이 매겨져 있고, 상점에서는 특별 제안(Special Offer)이라 불리는 할인 행사도 함께 진행하고 있습니다. 하나의 특별 제안은 서로 다른 종류의 상품을 한 개 이상 묶어 할인된 가격에 판매하는 형태입니다.
우리에게는 세 가지 정보가 주어집니다. 상품별 가격 목록(price), 특별 제안 목록(special), 그리고 각 상품을 정확히 몇 개씩 구매해야 하는지를 나타내는 목록(needs)입니다. 이때 특별 제안을 최적으로 활용하여 필요한 상품을 모두 구매할 때 지불해야 하는 최소 금액을 구하는 것이 이번 문제의 목표입니다.
각 특별 제안은 배열 형태로 표현됩니다. 배열의 마지막 숫자는 해당 제안을 구매할 때 지불해야 하는 가격을 의미하고, 나머지 숫자들은 이 제안을 통해 얻을 수 있는 각 상품의 수량을 나타냅니다.
예시로 이해하기
입력이 [2,5], [[3,0,5],[1,2,10]], [3,2]라고 가정해 보겠습니다. 이때 출력은 14가 됩니다.
상점에는 A와 B 두 종류의 상품이 있으며, 가격은 각각 $2와 $5입니다. 특별 제안 1은 $5를 지불하면 3A와 0B를 받을 수 있고, 특별 제안 2는 $10을 지불하면 1A와 2B를 받을 수 있습니다.
구매해야 할 상품은 3A와 2B입니다. 이 경우 특별 제안 2($10)로 1A와 2B를 구매한 뒤, 남은 2A는 개별 가격($2 × 2 = $4)으로 구매하는 것이 가장 저렴합니다. 따라서 총 지불 금액은 $10 + $4 = $14가 됩니다.
풀이 접근 방법
이 문제는 메모이제이션(Memoization)을 적용한 깊이 우선 탐색(DFS)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 먼저 모든 상품을 개별 가격으로 구매하는 경우를 기본값으로 계산해 둔 뒤, 사용 가능한 특별 제안을 하나씩 적용해 보며 더 저렴한 조합을 찾아내는 것입니다. 동일한 '필요 수량' 상태가 반복해서 등장할 수 있으므로, 한 번 계산한 결과를 맵(map)에 저장해 두면 중복 연산을 크게 줄일 수 있습니다.
구체적인 단계는 다음과 같습니다.
- 메모이제이션용 맵
memo를 정의합니다. - price와 needs 배열을 인자로 받는
directPurchase()메서드를 정의합니다. ret := 0으로 초기화합니다.- i를 0부터 price 배열 크기 − 1까지 반복하면서
ret := ret + price[i] * needs[i]를 수행합니다. - ret을 반환합니다. 즉, 할인 없이 모든 상품을 개별 가격으로 구매할 때의 총액입니다.
다음으로 price 배열, special 행렬, needs 배열, 시작 인덱스 idx를 인자로 받는 헬퍼(helper) 메서드를 정의합니다.
- memo에 이미 needs 상태가 저장되어 있다면
memo[needs]를 즉시 반환합니다. ret := directPurchase(price, needs)로 초기화합니다.- i를 idx부터 special 행렬의 행 개수 − 1까지 반복합니다.
- needs[j] < special[i][j]인 경우가 있으면 ok := false로 설정하고 내부 루프를 빠져나갑니다. 해당 제안으로는 필요 수량을 충족할 수 없다는 뜻입니다.
- 그렇지 않으면 temp 배열에
need[j] − special[i][j]를 삽입합니다. 제안 적용 후 남은 필요 수량입니다.
- ok가 true라면, 즉 해당 특별 제안을 적용할 수 있다면
op1 := special[i]의 마지막 원소 + helper(price, special, temp, i)ret := min(ret, op1)
memo[needs] := ret을 저장한 뒤 반환합니다.
마지막으로 main 메서드에서는 helper(price, special, needs, 0)을 호출해 결과를 반환합니다. 재귀 호출 시 현재 인덱스 i부터 탐색을 이어가기 때문에, 동일한 제안 조합을 중복해서 검토하는 비효율을 자연스럽게 피할 수 있습니다.
C++ 구현 코드
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
map <vector <int> , int> memo;
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
return helper(price, special, needs, 0);
}
int helper(vector <int>& price, vector < vector <int> >& special, vector <int>& needs, int idx){
if(memo.count(needs)) return memo[needs];
int ret = directPurchase(price, needs);
for(int i = idx; i < special.size(); i++){
vector <int> temp;
bool ok = true;
for(int j = 0; j < special[i].size() - 1; j++){
if(needs[j] < special[i][j]) {
ok = false;
break;
}
temp.push_back(needs[j] - special[i][j]);
}
if(ok){
int op1 = special[i][special[i].size() - 1] + helper(price, special, temp, i);
ret = min(ret, op1);
}
}
return memo[needs] = ret;
}
int directPurchase(vector <int>& price, vector <int>& needs){
int ret = 0;
for(int i = 0; i < price.size(); i++){
ret += price[i] * needs[i];
}
return ret;
}
};
main(){
vector<int> v1 = {2,5};
vector<vector<int>> v2 = {{3,0,5},{1,2,10}};
vector<int> v3 = {3,2};
Solution ob;
cout << (ob.shoppingOffers(v1, v2, v3));
}
실행 결과
입력:
[2,5] [[3,0,5],[1,2,10]] [3,2]
출력:
14
위 코드는 먼저 할인 없이 구매하는 경우를 기준값으로 잡고, 적용 가능한 특별 제안을 재귀적으로 조합해 가면서 최솟값을 갱신합니다. 메모이제이션 덕분에 동일한 필요 수량 상태에 대한 계산은 한 번만 수행되므로, 탐색 범위가 넓은 입력에서도 성능이 크게 향상됩니다.