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

<조건 분석>

 

1. N개의 식재료 중에서 골라서 경우의 수 따지는 문제임.

2. N이 15이하 이므로 비트마스킹으로 접근해볼 수 있겠음.

3. 그러면 최대 시간복잡도가 2^15정도니까 충분함.

 

<문제 해결 포인트>

 

1. 비트마스킹 로직은 흔한 비트마스킹 로직이라 괜찮음.

2. 출력이 문제인데, 오름차순 + 같은 비용의 집합이 하나 이상이면 사전 순 출력임.

3. map으로 (최소 비용, idx배열을 담는 vector) 쌍으로 관리해서 집합을 사전 순 정렬하면 됨.

 

 

출력이 .. 좀 ... 재미없다 ..  

#include <bits/stdc++.h>
using namespace std;

struct diet
{
    int p;
    int f;
    int s;
    int v;
    int price;
};

int N;
int mp, mf, ms, mv;
int res = 987654321;
vector<diet> v;
map<int, vector<vector<int>>> resv;


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> N;

    cin >> mp >> mf >> ms >> mv;

    int tp, tf, ts, tv, tprice;
    for (int i = 0; i < N; i++)
    {
        cin >> tp >> tf >> ts >> tv >> tprice;
        v.push_back({tp, tf, ts, tv, tprice});
    }

    vector<int> tempidx;
    for (int i = 0; i < (1 << N); i++)
    {
        int tempp = 0;
        int tempf = 0;
        int temps = 0;
        int tempv = 0;
        int tempprice = 0;
        tempidx.clear();
        for (int j = 0; j < N; j++)
        {
            if (i & (1 << j))
            {
                tempp += v[j].p;
                tempf += v[j].f;
                temps += v[j].s;
                tempv += v[j].v;
                tempprice += v[j].price;
                tempidx.push_back(j);
            }
        }

        if (tempp >= mp && tempf >= mf && temps >= ms && tempv >= mv)
        {
            if (res >= tempprice)
            {
                res = tempprice;
                resv[res].push_back(tempidx);
            }
        }
    }

    ::sort(resv[res].begin(), resv[res].end());

    if (res == 987654321) cout << -1;
    else
    {
        cout << res << "\n";
        for (auto item : resv[res][0])
        {
            cout << item + 1 << " ";
        }
    }

    return 0;
}