[BOJ 19942] 다이어트

썸네일

방금 배운 비트마스킹 을 활용하여 백준 문제를 풀어보자!

19942번: 다이어트

 

문제 설명

예제

1번은 식재료 1, 3, 5를 골랐을 때이고, 2번은 식재로 2, 3, 4를 골랐을 때이다.

둘 다 최소 영양성분 100, 70, 90, 10 이상을 만족하지만 총 가격은 1번이 270, 2번이 180으로

2번을 골랐을 때가 가격이 더 저렴하므로 더 나은 선택이 된다.

 

구현 아이디어

각 재료의 선택 여부를 0과 1로 나타내면 6자리 이진수로 모든 경우의 수를 나타낼 수 있다.

ex) 111000 - 식재료 1, 2, 3 선택

 

그러므로 반복문과 비트마스킹을 통해 모든 경우의 수를 완전 탐색을 진행해주면 된다.

만약 최소 영양 성분 조건을 충족하였을 경우의 비용을 계산하고, 기존 최소 비용보다 현재의 비용이 더 저렴하다면 최소 비용을 갱신하여 최종 최소 비용을 구하면 된다.

 

전체 코드

for (int i = 1; i < (1 << n); ++i) {
}

모든 경우의 수는 000000(0)부터 111111(63)이므로 i의 범위가 [0, 64)일 때로 반복문을 돌면 된다.

64를 비트마스킹으로 나타내면 1 << 6 (= 1000000) 이다.

 

map<int, vector<vector<int>>> rv; // 같은 비용의 집합

// 180: {{0,1,2}, {2,4,5}}

같은 비용의 집합을 표현하기 위해 2차원 배열을 value로 하는 맵 rv를 사용했다.

만약 가격이 180인 집합이 0, 1, 2와 2, 4, 6이라면 rv는 주석과 같은 형태가 될 것이다.

 

#include <bits/stdc++.h>

using namespace std;

#define INF 987654321

int n; // 식재료의 개수
int mp, mf, ms, mv; // 단백질, 지방, 탄수화물, 비타민 최소 영양성분
int p, f, s, v, c; // 단백질, 지방, 탄수화물, 비타민, 가격
int rc = INF; // 최소 비용
map<int, vector<vector<int>>> rv; // 같은 비용의 집합

vector<vector<int>> arr;

int main() {
    cin >> n;
    cin >> mp >> mf >> ms >> mv;

    for (int i = 0; i < n; ++i) {
        cin >> p >> f >> s >> v >> c;
        arr.push_back({p, f, s, v, c});
    }

    for (int i = 1; i < (1 << n); ++i) {
        int sum = 0; // 최소 비용
        int sp = 0, sf = 0, ss = 0, sv = 0;
        vector<int> v; // 식재료 집합
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) { // j번째 비트가 켜져있다면
                v.push_back(j + 1); // 비트가 켜져있을 경우 집합에 추가
                sum += arr[j][4]; // 비용
                sp += arr[j][0]; // 단백질
                sf += arr[j][1]; // 지방
                ss += arr[j][2]; // 탄수화물
                sv += arr[j][3]; // 비타민
            }
        }
        // 모든 최저 영양소 기준 통과
        if (sp >= mp && sf >= mf && ss >= ms && sv >= mv) {
            if (rc >= sum) {
                rc = sum;
                rv[rc].push_back(v);
            }
        }
    }

    if (rc == INF) cout << -1 << "\n";
    else { // 사전순으로 가장 빠른 것 출력
        sort(rv[rc].begin(), rv[rc].end());
        cout << rc << "\n";
        for (auto a : rv[rc][0]) {
            cout << a << " ";
        }
    }

    return 0;
}