[백준/BOJ] 백준 19942번 : 다이어트

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

19942번: 다이어트

 

모든 식재료를 확인하며 해당 식재료를 고르는 경우와 고르지 않는 경우를 완전 탐색(브루트 포스)하여 문제를 해결했다. 이때 조건을 만족하고 이전의 최소 비용과 같은 최소비용을 찾았다면 사전 순으로 앞서는 것을 골라야 하는데, 이때 백터끼리 대소 비교로 사전 순으로 앞서는 것을 판별했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
int mp, mf, ms, mv;
vector<int> p, f, s, v, c;
int result1 = 987654321;
vector<int> result2;

void Solve(vector<int>& selected, int index)
{
	//다 확인 했을때
	if (index >= n) {
		
		int p_sum = 0;
		int f_sum = 0;
		int s_sum = 0;
		int v_sum = 0;
		int c_sum = 0;
		for (int i = 0; i < selected.size(); i++) {
			p_sum += p[selected[i]];
			f_sum += f[selected[i]];
			s_sum += s[selected[i]];
			v_sum += v[selected[i]];
			c_sum += c[selected[i]];
		}

		//조건에 만족할때
		if (p_sum >= mp && f_sum >= mf && s_sum >= ms && v_sum >= mv) {
			if (result1 > c_sum) { //최소 비용을 찾았을때
				result1 = c_sum;
				result2 = selected;
			}
			else if (result1 == c_sum) { //이전의 최소 비용과 같을때 -> 사전순으로 앞선것을 고른다
				if (selected < result2) { //백터끼리 대소 비교로 사전순으로 앞서는지 확인
					result2 = selected;
				}
			}
		}

		return;
	}

	//index번째 식재료를 고를때
	selected.push_back(index);
	Solve(selected, index + 1);
	selected.pop_back();

	//index번째 식재료를 고르지 않을때
	Solve(selected, index + 1);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

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

	for (int i = 0; i < n; i++) {
		int pi, fi, si, vi, ci;
		cin >> pi >> fi >> si >> vi >> ci;
		p.push_back(pi);
		f.push_back(fi);
		s.push_back(si);
		v.push_back(vi);
		c.push_back(ci);
	}

	vector<int> selected;
	Solve(selected, 0);

	if (result1 == 987654321)
		result1 = -1;

	cout << result1 << "\n";
	for (int i = 0; i < result2.size(); i++) {
		cout << result2[i] + 1 << " "; //문제에서 식재료의 번호는 1번부터 시작
	}
}