[백준 19942번/ C++] 다이어트

해당 문제는 map과 비트마스킹을 이용해서 풀면된다.

 

조건에서 N은 3이상 15이하라고 하였으니 N이 5일때를 가정하고 한번 풀어보자. 

 

N이 5라는 것은 데이터가 들어있는 표의 개수가 총 5개라는 뜻이다.  

 

해당 문제는 각 표의 데이터값을 하나하나 다 더해서 조건식을 만족하는지 체크를 하는것이다. 

그렇기 때문에 비트마스킹을 활용하는것이다. 

 

N이 5라면 비트는 5개지만 나타낼수 있는 수는 총 2^5개가 만들어진다. 

 

예를 들어 00001, 00010, 00011, ... , 11110, 11111 이런것이 만들어질텐데 

비트가 1인것은 각 표의 튜플(행)을 보라는 뜻이다. 

즉, 00101 이라면 첫번째 데이터값과 세번째 데이터값들을 더해서 각 영양분이 최소 영양성분이 되냐를 따지면 된다.

만약 11111 이라면 각 영양성분들을 다 더해서 최소 영양성분이 되냐를 따지면 된다는 뜻이다.

 

만약, 최소 영양성분을 다 만족한다면 더해진 가격을 Key로 갖는 map을 만들어 각 인덱스 값을 벡터에 저장시켜 

Key값에 매칭 시킨다. 

 

해당 값들을 모두 탐색 했다면 제일 최소 가격 Key 값을 가지는 map 을 확인하고 해당 map에 벡터가 여러개 존재한다면 sort() 함수를 활용해서 사전순으로 정렬 한 후 가장 앞에 위치한 벡터의 값을 출력시킨다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <climits>
using namespace std;
int max_n = INT_MAX; 
int mp, mf, ms, mv, n;
int mp_sum, mf_sum, ms_sum, mv_sum, mc_sum;
map <int, vector<vector<int>>> m;
struct node{
    int p, f, s, v, c;
};
int main() {
    node data[15]; //구조체 배열 생성. N은 총 15개 이하
    cin >>n>>mp>>mf>>ms>>mv;
    for (int i = 0; i < n; i++) {
        cin >> data[i].p >> data[i].f >> data[i].s >> data[i].v >> data[i].c;
    } 
    for (int i = 1; i < (1 << n); i++) {          
        mp_sum = mf_sum = ms_sum = mv_sum = mc_sum = 0; 
        vector <int> v; 
        for (int j = 0; j < n; j++) {
            if (i & (1<<j)) { // 1을 shift 연산자를 통해 옮겨가면서 비트체킹
                mp_sum += data[j].p; 
                mf_sum += data[j].f; 
                ms_sum += data[j].s; 
                mv_sum += data[j].v; 
                mc_sum += data[j].c; 
                v.push_back(j+1); 
            }
        }
        if (mp_sum >= mp && mf_sum >= mf && ms_sum >= ms && mv_sum >= mv) {
            if (max_n >= mc_sum) {
                max_n = mc_sum; 
                m[mc_sum].push_back(v); 
            }
        }
    }
    if (max_n == INT_MAX) {
        cout << "-1"<<"\n"; 
    }
    else {
        cout << max_n << "\n";
        sort(m[max_n].begin(), m[max_n].end());
        for (int x : m[max_n][0]) {
            cout << x << " ";
        }
    }  
    return 0; 
}

19942번: 다이어트