24954 물약 구매(백준)

문제 생각 과정

만약 물약 종류가 정해진 물략 종류 이상을 넘어가면(기저조건),

벡터 하나 더 만들어서 복사하고,

a,b 짝 만들어서 cost[a] - b로 최대 할인율 적용해서 res에 더해주기 

그리고 최종 결괏값음 최소 물약갯수니 min(res, ans) 로 저렴하게 구매한 물약 동전개수 구해줌.

 

밑에는 1부터 n까지 루프돌리고 기본 bt format에 벡터만 상황에 맞게 push하거나 pop 하면 된다. 

 

코드

#include <iostream>
#include <vector>
#include <utility> //Pair
using namespace std;
const int MAX_N = 13;
int n;
int p[MAX_N];
int c[MAX_N];
int cost[MAX_N];
int aj;
int dj;
bool check[MAX_N];

int answer = 1e6;
vector<int> order;
vector<pair<int, int>> ad[MAX_N];

void backtrack(int depth){

    if (depth == n + 1){ //기저조건 depth 가 물약의 종류 이상을 넘어갈떄
        for(int i = 1; i <= n; i++){
            cost[i] = c[i];
        }
        int result = 0;
        for (auto i: order){
            for (auto [a , b]: ad[i]){
                cost[a] = max(cost[a] - b, 1); //최대 할인을 cost 배열에 적용
            }   
            result += cost[i];
        }
        //cerr << result;
        answer = min(result, answer); //가장 '저렴하게' 구매한 물약의 동전 개수
        return;
    }

    for (int i = 1; i <= n; i++){ //기본 bt format

        if (!check[i]){
            check[i] = true; 
            order.push_back(i);
            backtrack(depth + 1);
            check[i] = false;
            order.pop_back();
        }
    }

}

int main(){

    cin >> n;

    for (int i = 1; i <= n; i++){
        cin >> c[i];
    }

    for (int k = 1; k <= n; k++){
        cin >> p[k];
        for (int j = 1; j <= p[k]; j++){
            cin >> aj >> dj;
            ad[k].push_back(make_pair(aj, dj));
        }

    }
    backtrack(1);
    cout << answer;


}