[BeakJoon 19942] 다이어트

안녕하세요. 오늘은 백준 19942 다이어트 문제를 풀어보도록 하겠습니다.

 

해당 문제는 

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

19942번: 다이어트

 

위 링크에서 확인하실 수 있습니다.

 

 

저는 다음의 알고리즘으로 이 문제를 해결하였습니다.

 

1. 각 함수마다 두 개의 재귀 함수를 호출하였습니다. 해당 idx의 item을 선택한 경우, 선택하지 않은 경우를 나누어 호출하였습니다.

2. idx가 n까지 진행되었다면, 다음 두 가지의 경우로 결과를 초기화 해 주었습니다.

   1) 현재 선택된 item들의 가격의 합이 결과보다 적다면 -> 결과를 현재 값으로 바꾸어 줍니다.

   2) 현재 선택된 item들의 가격의 합과 결과가 같다면 -> 우선순위를 고려하여 결과를 현재 값으로 바꾸어 줍니다.

 

* 우선순위는 각각 string으로 변형하여, 사전 순으로 결정하였습니다.

* 각 재귀 함수마다 비트 마스킹을 활용하여 추가할지, 말지 결정하였습니다. 

 

<소스 코드>

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

typedef struct __struct {
	int p, f, s, v;
	int cost;	
}item;

vector<item> vec;

int n, mp, mf, ms, mv;
int res = 99999999, res_path = 99999999;
bool check(int path) {
	int p = 0, f = 0, s = 0, v = 0;
	for(int i = 0; i < n; i++) {
		if((1<<i)&path) p+=vec[i].p, f+=vec[i].f, s+=vec[i].s, v+=vec[i].v;
	}
	
	if(p >= mp && f >= mf && s >= ms && v >= mv) return true;
	return false;
}
bool check_priority(int path) {
	string a = "", b = "";
	for(int i = 0; i < n; i++) {
		if(res_path&(1<<i)) a+=to_string(i);
		if(path&(1<<i)) b+=to_string(i);
	}
	
	return a > b;
}
int calc(int path) {
	int cost = 0;
	for(int i = 0; i < n; i++) {
		if((1<<i)&path) cost += vec[i].cost;
	}
	return cost;
}
void go(int idx, int path) {
	if(idx > n) {
		if(check(path)) {
			int cost = calc(path);
			if(cost < res || (cost == res && check_priority(path))) res = cost, res_path = path;
		}
		return;	
	}
	
	go(idx+1, path|(1<<idx));
	go(idx+1, path);
}
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	
	cin >> mp >> mf >> ms >> mv;
	
	for(int i = 0; i < n; i++) {
		item vv;
		cin >> vv.p >> vv.f >> vv.s >> vv.v >> vv.cost;
		vec.push_back(vv);
	}
	
	
	go(0, 0);
	
	if(res == 99999999) cout << -1;
	else {
		cout << res << "\n";
		for(int i = 0; i < n; i++) if(res_path&(1<<i)) cout << i+1 << " ";	
	}

	return 0;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.