[BOJ 19942] 다이어트

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

19942번: 다이어트

 

- 문제 요약

 

식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다.

입력으로 식재료 표가 주어졌을 때, 최저 영양소 기준을 만족하는 최소 비용의 식재료 집합을 찾아야 한다.

 

 

- 알고리즘 정리

 

N이 15로 매우 작은 값이므로 재귀적으로 계속 돌려주면 됩니다.

 

 

- 코드 작성

 

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

struct st{
	int p,f,s,v,c;
};
int N,mp,mf,ms,mv,w=987654321;
vector<int>vec,result;
st arr[15];

void ff(int n,int p,int f,int s,int v,int c){
	if(n==N){
		if(p>=mp&&f>=mf&&s>=ms&&v>=mv){
            if(w>c){
                result=vec;
                w=c;
            }
			else if(w==c&&result>vec){
                result=vec;
                w=c;            
            }
        }
        return;
	}
	ff(n+1,p,f,s,v,c);
    vec.push_back(n);
    ff(n+1,p+arr[n].p,f+arr[n].f,s+arr[n].s,v+arr[n].v,c+arr[n].c);
    vec.pop_back();
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int p,f,s,v,c;
	cin>>N>>mp>>mf>>ms>>mv;
	for(int i=0;i<N;i++){
		cin>>arr[i].p>>arr[i].f>>arr[i].s>>arr[i].v>>arr[i].c;
	}
	ff(0,0,0,0,0,0);
	if(w==987654321){
		cout<<-1;
		return 0;
	}
	cout<<w<<'\n';
	for(auto i:result){
		cout<<i+1<<" ";
	}
}

코드 제출 결과