[백준]도영이가 만든 맛있는 음식(2961) C++ - 조합

https://www.acmicpc.net/problem/2961

🧐 문제

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

입력

첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

출력

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다.

🐥풀이방식

next_permutation을 이용해서 만들 수 있는 조합을 만들고 모든 조합에 대해 신맛과 쓴맛의 차이를 계산하였다.

vector<vector<int>> makeCombination() {
    vector<vector<int>> combinations;
    
    vector<int> candidates;  // 0-1-2-3
    for (int i = 0; i < n; ++i) {
        candidates.push_back(i);
    }
    
    for(int i = 1; i<= n; i++) {
        vector<int> tmp(n-i,0);
        for(int j = 0; j < i; j++)
            tmp.push_back(1);
        
        do{
            vector<int> indexs;
            for(int k = 0; k < n; k++) {
                if(tmp[k])
                    indexs.push_back(candidates[k]);
            }
            combinations.push_back(indexs);
        }while(next_permutation(tmp.begin(), tmp.end()));
    }
    return combinations;
}

👉🏻조합을 만드는 코드이다. 이 문제에서 조합을 만들어야하는 벡터가 pair형식이기 때문에 이를 대체하여 재료의 개수 별로 따로 벡터를 만들어주었다.
next_permutation에서 조합을 만드는 방법은 전에 작성한 게시물을 참고하자!!
ex) {0,0,1,1} 인 경우 => 2개씩 포함하는 경우의 수를 만든다.
위의 코드 처럼 0과1의 개수에 따라 해당하는 조합을 만들고 combinations벡터에 넣어준다.
그 후, 만든 조합을 다시 탐색하면서 신맛과 쓴맛의 차이를 계산해주면 된다.

전체코드

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

using namespace std;
int n;
vector<pair<int,int>> v;

vector<vector<int>> makeCombination() {
    vector<vector<int>> combinations;
    
    vector<int> candidates;  // 0-1-2-3
    for (int i = 0; i < n; ++i) {
        candidates.push_back(i);
    }
    
    for(int i = 1; i<= n; i++) {
        vector<int> tmp(n-i,0);
        for(int j = 0; j < i; j++)
            tmp.push_back(1);
        
        do{
            vector<int> indexs;
            for(int k = 0; k < n; k++) {
                if(tmp[k])
                    indexs.push_back(candidates[k]);
            }
            combinations.push_back(indexs);
        }while(next_permutation(tmp.begin(), tmp.end()));
    }
    return combinations;
}

int calDiff() {
    vector<vector<int>> combinations = makeCombination();
    
    int min = 2147483647;
    
    for (int i = 0; i < combinations.size(); ++i) {
            int sour = 1, bitter = 0;

            // 각 조합별로 신맛, 쓴맛 계산
            for (int j = 0; j < combinations[i].size(); ++j) {
                int idx = combinations[i][j];
                sour *= v[idx].first;
                bitter += v[idx].second;
            }

            // 신맛, 쓴맛 차이 계산 후 최솟값이면 갱신
            int diff = abs(sour-bitter);
            if (min > diff){
                min = diff;
            }
        }
        return min;
}


int main() {
    
    cin >> n;

    for(int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        v.push_back({x,y});
    }

    cout << calDiff() << endl;
    
    
    return 0;
}

🕶 회고
조합을 만드는 방식은 알고 있었지만, pair형태에 벡터가 나오니 복잡하게 생각하였다. 1차원으로 변형하는 방식을 기억해야겠다.