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

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

 

문제 설명

입력으로 식재료 표가 제공되었을 때, 최저 영양소 기준을 만족하는 최소 비용의 식재료 집합을 찾는 문제이다.

 

주요 로직

1. 최소 비용을 찾아야 한다.
-> 완전탐색을 이용해 모든 집합을 다 찾고 각각의 집합의 경우에 대한 비용을 구한 후 최소 비용을 찾는다
2. 최소 비용인 경우의 집합 구하기
-> map이라는 자료 구조를 사용해서 모든 집합의 경우를 다 저장해 둔 후, 최소 비용의 경우에 대해서만 정렬을 해서 첫 값을 뽑도록 구현했다. 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

struct A{
	int a,b,c,d,e;
};

int n,a,b,c,d,e,ret=987654321;
int arr[4];
vector<A> v;
map<int, vector<vector<int>>> mp;

void dfs(int idx, int a, int b, int c, int d, int e, vector<int> vv){
	if(idx == n){
		if(a >= arr[0] && b >= arr[1] && c >= arr[2] && d >= arr[3]){
		ret = min(ret, e);
		mp[e].push_back(vv);
		}
		return;
	}
	if(a >= arr[0] && b >= arr[1] && c >= arr[2] && d >= arr[3]){
		ret = min(ret, e);
		mp[e].push_back(vv);
	}
	// idx 번째를 획득하는 경우
	vv.push_back(idx+1);
	dfs(idx+1, a+v[idx].a, b+v[idx].b, c+v[idx].c, d+v[idx].d, e+v[idx].e, vv);
	vv.pop_back();
	
	// idx 번째를 획득하지 않는 경우 
	dfs(idx+1, a, b, c, d, e, vv);
	return ;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for(int i=0; i<4; i++){
		cin >> arr[i];
	}
	for(int i=0; i<n; i++){
		cin >> a >> b >> c >> d >> e;
		v.push_back({a,b,c,d,e});	
	}
	vector<int> vv;
	dfs(0,0,0,0,0,0,vv);
	
	sort(mp[ret].begin(), mp[ret].end());

	if(ret == 987654321) cout << "-1\n";
	else{
		cout << ret << "\n";
		for(auto it : mp[ret][0]){
			cout << it << " ";
		}
		cout << "\n";
	} 
}