[ 백준 / C++ ] 2961 : 도영이가 만든 맛있는 음식

[ 문제 ]

 

2961번: 도영이가 만든 맛있는 음식

 

[ 접근방법 ]

 

n이 최대 10 이므로 백트래킹으로도 충분히 가능하다.

 

재료 사용 여부를 비트마스크를 통해 처리했다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int n;
vector<pair<int, int>> taste;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    taste.resize(n);

    for(int i = 0; i < n; i++){
        cin >> taste[i].first >> taste[i].second;
    }

    int ans = 1e9;

    for(int i = 1; i < (1 << n); i++){
        int a = 1, b = 0;

        for(int j = 0; j < n; j++){
            if(i & (1 << j)){
                a *= taste[j].first;
                b += taste[j].second;
            }
        }

        ans = min(ans, abs(a - b));
    }

    cout << ans;

    return 0;
}