백준 19942번 다이어트 ( C++ )

문제

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

 

해설

비트마스킹 관련 기본적인 문제

map을 이용해 vector<vector>>를 구현

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
 
const int INF = 987654321;
int n, ret = INF, mp, mf, ms, mv, p[19], f[19], s[19], v[19], c[19];
 
map<int, vector<vector<int>>> retNum;
 
void go(int num)
{
  int tp = 0, tf = 0, ts = 0, tv = 0, tmp = 0;
  vector<int> tmpNum;
  for (int i = 0; i < n; i++)
  {
    if (num & (1 << i))
    {
      tp += p[i];
      tf += f[i];
      ts += s[i];
      tv += v[i];
      tmp += c[i];
      tmpNum.push_back(i + 1);
    }
  }
  if (tp >= mp && tf >= mf && ts >= ms && tv >= mv && ret >= tmp)
  {
    ret = min(ret, tmp);
    retNum[tmp].push_back(tmpNum);
  }
}
 
int main()
{
  cin >> n;
  cin >> mp >> mf >> ms >> mv;
  for (int i = 0; i < n; i++)
  {
    cin >> p[i] >> f[i] >> s[i] >> v[i] >> c[i];
  }
 
  for (int i = 1; i < (1 << n); i++)
  {
    go(i);
  }
  if (ret == INF)
  {
    cout << -1 << "\n";
    return 0;
  }
  cout << ret << "\n";
  sort(retNum[ret].begin(), retNum[ret].end());
  for (int i : retNum[ret][0])
  {
    cout << i << " ";
  }
}