[Algorithm]Baekjoon 19942번 :: 다이어트

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
struct Food
{
    int p, f, s, v, c;
};
 
int n, mp, mf, ms, mv;
vector<Food> foods(16);
const int maxNum = 0x3f3f3f3f;
int answer = maxNum;
 
vector<int> curRoute;
vector<int> answerRoute;
 
 
void DFS(int index, int p, int f, int s, int v, int c)
{
    if (p >= mp && f >= mf && s >= ms && v >= mv)
    {
        if (c < answer)
        {
            answer = c;
            answerRoute = curRoute;
        }
        
        return;
    }
 
    if (index == n) return;
 
    // 선택
    curRoute.push_back(index + 1);
    DFS(index + 1, p + foods[index].p, f + foods[index].f, 
        s + foods[index].s, v + foods[index].v, c + foods[index].c);
    curRoute.pop_back();
 
    // 안선택
    DFS(index + 1, p, f, s, v, c);
}
 
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)
    {
        cin >> foods[i].p >> foods[i].f >> foods[i].s >> foods[i].v >> foods[i].c;
    }
 
    DFS(0, 0, 0, 0, 0, 0);
 
    if (answer == maxNum) cout << -1;
    else
    {
        cout << answer << endl;
 
        for (int i = 0; i < answerRoute.size(); ++i)
        {
            printf("%d ", answerRoute[i]);
        }
    }
}
 
 

 

골드4지만 정답률이 25%길래 한번 풀어봤는데, 딱히 특별하게 다른 문제는 아니였다.

각 식품을 선택,안선택하면서 완전탐색을 진행하면 되고, 루트도 알아야하기 때문에 선택할때마다 푸쉬해서 answer를 갱신할 때, 갱신할만하면 answerRoute에 복사해주면 된다.

 

N값이 작아서 충분히 0ms로 통과한다.