[백준 c++] 19942 다이어트

문제 설명

https://www.acmicpc.net/problem/19942
식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각각 합이 최소 100, 70, 90, 10가 되도록 하는 경우를 생각해보자. 이 경우 모든 재료를 선택하면 쉽게 해결되지만, 우리는 조건을 만족시키면서도 비용이 최소가 되는 선택을 하려고 한다.

예를 들어, 식재료 1, 3, 5를 선택하면 영양분은 100, 145, 130, 10으로 조건을 만족하지만 가격은 270이 된다. 대신 2, 3, 4를 선택하면 영양분의 합은 110, 130, 90, 10, 비용은 180이 되므로, 앞의 방법보다는 더 나은 선택이 된다.
입력으로 식재료 표가 주어졌을 때, 최저 영양소 기준을 만족하는 최소 비용의 식재료 집합을 찾아야 한다.

입력
첫 줄에 식재료의 개수 $N$이 주어진다.
다음 줄에는 단백질, 지방, 탄수화물, 비타민의 최소 영양성분을 나타내는 정수 $mp$, $mf$, $ms$, $mv$가 주어진다.

이어지는 $N$개의 각 줄에는 $i$번째 식재료의 단백질, 지방, 탄수화물, 비타민과 가격이 5개의 정수 $p_i$, $f_i$, $s_i$, $v_i$, $c_i$와 같이 주어진다. 식재료의 번호는 1부터 시작한다.

출력
첫 번째 줄에 최소 비용을 출력하고, 두 번째 줄에 조건을 만족하는 최소 비용 식재료의 번호를 공백으로 구분해 오름차순으로 한 줄에 출력한다. 같은 비용의 집합이 하나 이상이면 사전 순으로 가장 빠른 것을 출력한다.
조건을 만족하는 답이 없다면 -1을 출력하고, 둘째 줄에 아무것도 출력하지 않는다.

아이디어

N가지 중 식재료를 고르는 경우의 수는 2^n -1가지다.
만약 N=6이라면 총 6가지의 식재료가 있고 1개부터 6개까지 골라 비트를 구성할 수 있다.
ex) 1번 식재료만 고르는 경우는 100000
1번 5번 식재료를 고르는 경우는 100010 이다.

모든 비트마스킹 경우의 수에서 해당 비트마스킹이 최저 영양소 기준을 만족하는지, 최저 비용인지 체크한다.

이 문제에서 추가로 주의해야할 점은 같은 비용의 집합이 하나 이상이면 사전 순으로 가장 빠른 것을 출력해야한다는 것이다.

3
0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0

위와 같은 입력일 때 최저 비용인 집합은 {3}, {1,2,3}이고 정답은 {1,2,3}이 된다.

가격은 최대 500이고 식재료 수는 3~15개로 최소 비용은 0~6000이다.
이 비용을 갖는 식재료 집합을 2차원 벡터 배열로 담아서 저장했다.

vector<vector<int>> result[6001]

ex) 0을 최소 비용으로 갖는 집합이 {3}, {1,2,3}일 때 result[0]={{3},{1,2,3}}
2차원 벡터를 sort하면 사전순으로 정렬이되고 result[0]을 출력하면 된다.

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, cost, flag, mx = 987654321, m_cost, nut[4], a[15][5];
vector<int> v;
vector<vector<int>> result[6001];
int main()
{
    cin >> n;
    for (int i = 0; i < 4; i++)
        cin >> nut[i];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            cin >> a[i][j];
        }
    }
    m_cost = mx;
    for (int i = 1; i < (1 << n); i++)
    {
        int ret[5] = {0, 0, 0, 0};
        flag = 1;
        cost = 0;
        for (int j = 0; j < n; j++)
        {
            if (i & (1 << j))
            {
                for (int k = 0; k < 4; k++)
                {
                    ret[k] += a[j][k];
                }
                cost += a[j][4];
                v.push_back(j + 1);
            }
        }
        for (int l = 0; l < 4; l++)
        {
            if (nut[l] > ret[l])
                flag = 0;
        }
        if (flag && cost <= m_cost)
        {
            result[cost].push_back(v);
            m_cost = cost;
        }
        v.clear();
    }
    if (m_cost == mx)
        cout << -1 << "\n";
    else
    {
        cout << m_cost << "\n";
        sort(result[m_cost].begin(), result[m_cost].end());
        for (int i : result[m_cost][0])
            cout << i << " ";
    }
}