백준 BOJ 19942 - 다이어트

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

19942번: 다이어트

N이 15로 작은편에 속하기 때문에

O(2^N) 브루트포싱을 사용해서도 문제를 해결할 수 있다.

브루트포스의 구현을 위해서 비트마스킹을 사용해줬다.

i번 비트가 켜진 경우가 i번 식재료를 선택하는 경우이다.

 

문제에서 까다로웠던 부분은

같은 비용의 집합이 하나 이상이면 사전 순으로 가장 빠른 것을 출력한다.

였는데,

정답이 담긴 벡터들을 관리할

vector<vector<int>> 구조를 하나 만들어서

정답 배열들이 담긴 배열을 정렬해주면

사전순으로 알아서 깔끔하게 정렬이 된다는듯 하다.

 

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

map<int,vector<vector<int>>> M;

int mp,mf,ms,mv;
int p[20] = {0};
int f[20] = {0};
int s[20] = {0};
int v[20] = {0};
int c[20] = {0};

int N;
int ans_c = 998244353;
vector<int> tmp;
vector<vector<int>> ans;

void calc(int bit){
	int np=0;
	int nf=0;
	int ns=0;
	int nv=0;
	int nc=0;
	
	for(int i=0; i<N; i++){
		if(bit & (1<<i)){
			np += p[i];
			nf += f[i];
			ns += s[i];
			nv += v[i];
			nc += c[i];
		}
	}
	if(np<mp || nf<mf || ns<ms || nv<mv) return;
	
	if(nc < ans_c) ans.clear();
	
	if(nc <= ans_c){
		ans_c = nc;
		tmp.clear();
		for(int i=0; i<N; i++){
			if(bit & (1<<i)){
				tmp.push_back(i+1);
			}
		}
		ans.push_back(tmp);
	}
	return;
}

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++) calc(i);
    
    sort(ans.begin(), ans.end());
    
    if(ans_c == 998244353){
		cout << -1;
		return 0;
	}
	
	cout << ans_c << "\n";
	for(auto k : ans[0]) cout << k << " ";
	return 0;
}