[백준] 24954번 : 물약 구매 (C++)

24954번 : 물약 구매

---

문제)

준겸이는 모험가이다. 모험을 떠나기 위해서는 철저한 사전 준비를 갖추어야 한다.

준겸이는 모험을 떠나기 전 N종류의 물약을 모두 구매하려고 한다. 물약 상점에 들른 준겸이는 각 물약이 1번부터 N번까지 번호가 매겨져 있다는 것을 알아냈다. 그런데, 물약 상점에서는 오늘 특별한 이벤트를 하고 있었다. 특정 물약을 구매하면, 어떤 다른 물약들을 할인해준다는 것이었다.

 

원래 i번째 물약의 가격은 동전 c_i개이다. 만약 i번째 물약을 구매하면, p_i종류의 다른 물약의 가격이 내려간다.

 

할인은 중첩된다. 예를 들어 1번 물약을 구매하면 3번 물약의 가격이 동전 1개만큼 할인되고, 2번 물약을 구매하면 역시 3번 물약의 가격이 동전 2개만큼 할인된다고 하자. 그러면 두 물약을 모두 구매하고 나서 3번 물약을 구매할 때 동전 3개만큼의 할인을 받을 수 있다. 단, 물약의 가격이 내려가더라도 0 이하로 내려가지는 않는다. 예를 들어, 원래 가격이 동전 5개인 물약이 동전 4개를 넘는 만큼 할인되더라도 가격은 동전 1개가 된다. 

 

준겸이는 신나서 물약을 구매하려다가, 물약을 구매하는 순서가 중요하다는 사실을 깨달았다. 준겸이를 위해 물약을 가장 싸게 샀을 때 그 비용을 알려주자.

 

 

 

입력 :

 

 

 

출력 :

첫째 줄에 물약을 가장 싸게 샀을 때 동전이 몇 개 필요한지 출력한다. 

 

 

 

 

 

풀이)

 

// 24954. 물약 구매
#include <iostream>
#include <vector>
#include <limits.h>
 
using namespace std;
 
int n;
vector<int> price;
vector<vector<pair<int, int>>> sale;
vector<bool> visited;
 
vector<int> vec;
int ans = INT_MAX;
void recur(int cur)
{
    // 조합이 완성되었다면
    if (cur == n)
    {
        int res = 0;
        // 원본 가격은 바꾸면 안되므로 복사한다.
        vector<int> temp = price;
        
        // 순서대로 물약을 구매하면서, 할인을 적용한다.
        for (int i = 0; i < n; i++)
        {
            int cur = vec[i];
            res += temp[cur];
 
            for (int j = 0; j < sale[cur].size(); j++)
            {
                int x = sale[cur][j].first;
                int y = sale[cur][j].second;
                temp[x] -= y;
                temp[x] = max(1, temp[x]);
            }
        }
 
        ans = min(ans, res);
        return;
    }
 
    // 물약에 대한 조합
    for (int i = 0; i < n; i++)
    {
        // 해당 물약을 구매했는지 아닌지.
        if (visited[i] == true) continue;
        visited[i] = true;
        vec[cur] = i;
        recur(cur + 1);
        visited[i] = false;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
 
    price.resize(n);
    sale.resize(n);
 
    vec.resize(n);
    visited.resize(n, false);
 
    for (int& ele : price) cin >> ele;
 
    int t, a, b;
    for (int i = 0; i < n; i++)
    {
        cin >> t;
        for (int j = 0; j < t; j++)
        {
            cin >> a >> b;
            sale[i].push_back(make_pair(a - 1, b));
        }
    }
 
    recur(0);
 
    cout << ans;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/24954 

24954번: 물약 구매