백준 19942번 : 다이어트(골드 4)

문제

풀이

입력으로 N개의 식재료가 주어지고 N개의 식재료 중 몇 개를 선택해서 최소의 비용으로 최소 영양분을 만족하는 식재료의 조합을 찾는 문제이다

N이 15까지이므로 재귀를 이용한 조합 문제로 풀었다

먼저 식재료를 구조체로 만들어 모든 식재료를 저장하는 벡터에 담은 뒤 N개의 식재료 중 1개를 선택, 2개를 선택 ,,, N개를 선택까지 조합 combi 벡터를 만들어 인덱스로 저장한 다음 조합의 길이가 depth와 같아지면 조건을 검사한다

최소 영양분을 만족하는 지 먼저 검사를 한다. 만약 만족한다면 비용을 구해 answer보다 작다면 인덱스들이 담긴 정답 벡터를 비우고 현재 combi를 추가한다

비용이 같다면 정답 벡터에 그대로 뒤에 추가한다

만약 조합을 구하다가 현재 조합의 비용이 정답보다 크다면 그냥 리턴해줬다(백트래킹)

모든 조합이 끝나고 정답 벡터가 남았을텐데 이게 비어있다면 조건을 만족못하므로 -1을 출력한다. 비어있지 않다면 최소 비용을 출력하고 정답 벡터를 오름차순으로 정렬해 첫 번째 정답의 인덱스들을 출력해준다

풀이

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

int N;
int mp, mf, ms, mv;
int answer = INT_MAX;
vector<vector<int>> answer_vector;

struct Ingredient
{
    int p;
    int f;
    int s;
    int v;
    int c;
};
vector<Ingredient> v;
vector<int> combi;

void Input()
{
    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;
        v.push_back({ pi, fi, si, vi, ci });
    }
}

bool Check()
{
    int sp = 0, sf = 0, ss = 0, sv = 0;

    for (int idx : combi)
    {
        sp += v[idx].p;
        sf += v[idx].f;
        ss += v[idx].s;
        sv += v[idx].v;
    }

    if (sp < mp || sf < mf || ss < ms || sv < mv) return false;

    return true;
}

int Cost()
{
    int cost = 0;

    for (int idx : combi)
    {
        cost += v[idx].c;
    }

    return cost;
}

void Func(int start, int depth)
{
    if (Cost() > answer) return;

    if (depth == combi.size())
    {
        if (Check())
        {
            int cost = Cost();
            if (answer > cost)
            {
                answer = cost;

                answer_vector.clear();
                answer_vector.push_back(combi);
            }
            else if (answer == cost)
            {
                answer_vector.push_back(combi);
            }
        }
        return;
    }

    for (int i = start; i < N; i++)
    {
        combi.push_back(i);
        Func(i + 1, depth);
        combi.pop_back();
    }
}

void Solve()
{
    for (int i = 1; i <= N; i++)
    {
        Func(0, i);
    }

    if (answer_vector.empty())
    {
        cout << -1;
    }
    else
    {
        cout << answer << '\n';

        sort(answer_vector.begin(), answer_vector.end());

        for (int idx : answer_vector[0])
        {
            cout << idx + 1 << ' ';
        }
    }
}

int main()
{
    Input();

    Solve();

    return 0;
}

회고

정답의 조건을 잘못 알아서 좀 틀렸다. 먼저 아무 조건을 만족못하면 -1을 출력하는 거에서 한 번과 최소 비용이 여러 개 있을 때 사전순으로 출력하는 거를 그냥 무시했다가

다음 반례를 통해 풀이를 고쳤다

input :
3
0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
output :
0
3
answer :
0
1 2 3