[비트마스킹 / BOJ 19942 / C++] 다이어트

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

19942번: 다이어트

1) 비트마스킹으로 식재료끼리의 조합을 구한다.
2) 구한 조합의 각각의 영양성분들끼리의 합이 최소 영양성분을 넘기는지 확인한다.
3) 최소 영양 성분을 넘긴다면, 이때의 비용과 식재료 조합을 vector에 저장한다. 
4) vector을 sort로 오름차순 정렬하여 가장 첫번째 조합을 출력한다.

문제를 읽어보면 어? 이거 조합아닌가? 라는 생각이 든다.

 

하지만 조합으로 풀면 매우 어려운 선택이 될 것이다.

 

식재료 N개 중에 1개를 뽑는 경우, 2개를 뽑는 경우, 3개를 뽑는 경우, .... N 개를 뽑는 경우까지 고려해야한다.

 

이 모두를 combination을 활용해 풀기에는 힘들다. 따라서

 

bit masking을 도입하여 풀어본다!!

 

bit masking의 의미는,

 

예를 들어 N개를 가지고서, 만들 수 있는 모든 조합의 개수를 구할 수 있다는 뜻이다.

 

{1, 2, 3, 4, 5, ... N} 이라는 집합이 있을 때, '1'이 없거나 있을 경우의 수, '2'가 없거나 있을 경우의 수...

 

총 만들 수 있는 조합의 수는 2^N 개이다 !!(물론 아무것도 선택하지 않는 경우 1이 있다!)

 

어쨋거나 이를 다시 비트로 표현하자면, 1000000..... 이라는 숫자를 가지고서 000000..00, 0000..01, 00000...10, 0000...11 

이런식으로 배열을 만들지 않고 비트로 있을 경우와 없을 경우를 표시해줄 수 있다!

 

이 로직을 생각하면, 나머지는 정말 쉽게 해결할 수 있다!

참고로 `i & (1 << j)` 의 의미는 주어진 i 비트에서, j번째 index의 값이 0인지 1인지 확인한다는 의미이다!

 

 

그리고 문제에서 오름차순으로 정렬할때, 가장 첫번째로 오는(사전순으로 가장 앞서는) 결과를 출력하라했으니

이 로직도 까먹지 말고 넣자!! (나는 이것때문에 한참해맸다...)

 

#include <bits/stdc++.h>

using namespace std;

int foods[20][6];
int now_nutri[6], min_nutri[6];
int cost, res=INT_MAX, N;
vector<pair<int, vector<int>>> ans;



int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    for(int j = 0 ; j < 4 ; j++){
        cin >> min_nutri[j]; // 0 1 2 3
    }
    
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < 5 ; j++){
            cin >> foods[i][j];
        }
    } // 가격 및 영양.
    
    for(int i=0 ; i < (1<<N) ; i++){
        
        vector<int> tmp;
        for(int j = 0 ; j < N ; j++){
            if(i & (1 << j)){
                for(int k = 0 ; k < 4 ; k++) {now_nutri[k] += foods[j][k];}
                cost += foods[j][4];
                tmp.push_back(j+1);
            }
        }
        
        int flag = 1;
        for(int k = 0 ; k < 4 ; k++){
            if(min_nutri[k]==0) continue;
            if(now_nutri[k] < min_nutri[k]) {flag = 0 ; break;}
        } // 개별 영양소 비교.
        
        
        if (flag && cost <= res){
            ans.push_back({cost,tmp});
        }
        
        cost = 0;
        memset(now_nutri, 0, sizeof(now_nutri));
    } // 경우의 수 구하기.
    
    if(!ans.empty()){
        sort(ans.begin(), ans.end());
        cout << ans[0].first << '\n';
        for(auto i : ans[0].second) cout << i << ' ';
    } else{
        cout << "-1";
    }
    
}