[백준OJ] 19942번 다이어트

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

19942번: 다이어트

---

 

풀이

음식들의 영양소를 모두 입력받은뒤에, 백트래킹을 이용하여 해당 음식을 선택했을때와 , 선택하지 않았을때의 경우를 모두 고려하여 매 함수 진입마다 최솟값을 갱신해주면된다.

 

시간복잡도

N개의 음식마다 선택의 길이 2가지 경우이므로, O(2¹⁵)가 된다.

 

코드

#include<iostream>
#include<algorithm>
#include<vector>
#define MAX 987654321
using namespace std;

//영양소
typedef struct node{
	int num, p, f, s, v, c;
}node;

int n, mp, mf, ms, mv,ret=MAX;
vector<int> ret_v;//최솟값의 음식번호를 저장하는 벡터
vector<int> temp_v;//임시벡터
vector<node> foods;
bool visited[15];

int isOver() {
	int sp, sf, ss, sv, sc;
	sp = sf = ss = sv = sc = 0;
	temp_v.clear();
	for (int i = 0; i < n; i++) {
		if (visited[i]) {
			sp += foods[i].p;
			sf += foods[i].f;
			ss += foods[i].s;
			sv += foods[i].v;
			sc += foods[i].c;
			temp_v.push_back(foods[i].num);
		}
	}
	if (sp >= mp && sf >= mf && ss >= ms && sv >= mv) {
		return sc;
	}
	else {
		return -1;
	}
}

void dfs(int ind) {
	int sum=isOver();
	if (sum!=-1&&ret>sum) {
		ret = min(ret, sum);
		ret_v = temp_v;
	}

	if (ind == n) {
		return;
	}
	visited[ind] = true;
	dfs(ind + 1);
	visited[ind] = false;
	dfs(ind + 1);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	cin >> mp >> mf >> ms >> mv;
	for (int i = 0; i < n; i++) {
		int p, f, s, v, c;
		cin >> p >> f >> s >> v >> c;
		foods.push_back({ i + 1,p,f,s,v,c });
	}
	dfs(0);
	if (ret == MAX) {
		cout << -1;
	}
	else {
		cout << ret << "\n";
		for (int i = 0; i < ret_v.size(); i++) {
			cout << ret_v[i] << " ";
		}
	}
	return 0;
}