19942 - 다이어트

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

19942번: 다이어트

과정

1. 단순 브루트 포스 문제이다.
2. 1번 식재료 부터 시작해 기록해 나가며 영양소 기준을 만족하면 더 이상 진행할 필요가 없어 종료시킨다.
3. 만족하는 것이 없다면 -1 을 출력하자.

코드

#include<iostream>
#include<string>

using namespace std;

int N;

int nut[16][5];
int minNut[4];
int ansCost = 987'654'321;
string ansStr;

void input(){
    cin>>N;
    cin>>minNut[0]>>minNut[1]>>minNut[2]>>minNut[3];
    for(int i=0;i<N;++i){
        cin>>nut[i][0]>>nut[i][1]>>nut[i][2]>>nut[i][3]>>nut[i][4];
    }
}

void dfs(int node, int cost, string chk, int mp, int mf, int ms, int mv){
    if(mp >= minNut[0] && mf >= minNut[1] && ms >= minNut[2] && mv >= minNut[3]){
        if(ansCost > cost){
            ansCost = cost;
            ansStr = chk;
        }
        return;
    }

    for(int i=node+1;i<N;++i){
        dfs(i,cost + nut[i][4], chk + to_string(i+1) + " ", mp+nut[i][0], mf+nut[i][1], ms+nut[i][2], mv+nut[i][3]);
    }
}

void solution(){
    for(int i=0;i<N;++i){
        dfs(i,nut[i][4],to_string(i+1) + " ", nut[i][0], nut[i][1], nut[i][2], nut[i][3]);
    }

    if(ansCost == 987'654'321){
        cout<<-1<<'\n';
    }
    else{
        cout<<ansCost<<'\n'<<ansStr<<'\n';
    }

    return ;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    solution();

    return 0;
}