[백준] 19942 다이어트 python C++

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

19942번: 다이어트

재료 중 몇개를 선택해서 영양분 각각 일정 이상이 되어야 하고 비용이 최소가 되어야한다.

N의 최대값이 15이므로 2^15 = 32768 이므로 완전탐색으로 모든 조합을 만들기로 판단했다.매번 리스트에 추가해서 내려보내는 방식으로 구현했다.

import sys; input = sys.stdin.readline

def list_chk(lst, goal, foods):
    # 최저 영양소 기준을 만족하는지 체크
    sum_val = [0 for _ in range(5)]
    for i in range(5):
        for j in range(len(lst)):
            sum_val[i] += foods[lst[j]][i]

        if i == 4: continue
        if sum_val[i] < goal[i]:
            return (False, None)

    return (True, sum_val[4])

def backtrack(ind, limit, foods, goal, lst=[]):
    list_answer_chk = list_chk(lst, goal, foods)
    if list_answer_chk[0]:
        global answer
        answer.append((list_answer_chk[1], lst))
        return
    if ind == limit:
        return
    backtrack(ind+1, limit, foods, goal, lst+[ind])
    backtrack(ind+1, limit, foods, goal, lst)

def main():
    N = int(input())
    goal = tuple(map(int, input().split()))
    foods = [tuple(map(int, input().split())) for _ in range(N)]
    global answer
    answer = []
    backtrack(0, N, foods, goal)
    if answer:
        answer.sort(key=lambda x:(x[0], ''.join(map(str, map(lambda y: y+1,x[1])))))
        print('{}\n{}'.format(answer[0][0],' '.join(map(str, map(lambda y: y+1,answer[0][1])))))
    else:
        print(-1)

if __name__ == '__main__':
    main()

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

vector< pair<int, string> > answer;

vector<int> list_chk(vector<int> list, vector<int> goal, vector< vector<int> > foods) {
    vector<int> sum_val(5, 0);
    vector<int> ret(2, 0);
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < list.size(); j++)
        {
            sum_val[i] += foods[list[j]][i];
        }
        if (i == 4) continue;
        if (sum_val[i] < goal[i]) {
            return ret;
        }
    }
    ret[0] = 1;
    ret[1] = sum_val[4];
    return ret;
}

void bt(int ind, int limit, vector< vector<int> > foods, vector<int> goal, vector<int> list) {
    vector <int> list_chk_val = list_chk(list, goal, foods);
    if (list_chk_val[0]) {
        string string_tmp = "";
        for (int i = 0; i < list.size(); i++) {
            string_tmp += to_string(list[i] + 1) + ' ';
        }
        pair<int, string> tmp(list_chk_val[1], string_tmp);
        answer.push_back(tmp);
    }
    if (ind == limit) return;

    vector<int> new_list;
    new_list = list;
    new_list.push_back(ind);
    bt(ind + 1, limit, foods, goal, new_list);
    bt(ind + 1, limit, foods, goal, list);

}

int main() {
    int N, tmp;
    vector <int> goal(4);
    cin >> N;
    vector< vector<int> > foods(N);
    for (int i = 0; i < 4; i++)
    {
        cin >> tmp;
        goal[i] = tmp;
    }
    for (int i = 0; i < N; i++)
    {
        vector<int> tmp_v(5);
        for (int j = 0; j < 5; j++)
        {
            cin >> tmp;
            tmp_v[j] = tmp;
        }
        foods[i] = tmp_v;
    }
    vector<int> tmp_list;
    bt(0, N, foods, goal, tmp_list);
    if (answer.size()) {
        sort(answer.begin(), answer.end());
        cout << answer[0].first << endl;
        cout << answer[0].second << endl;
    }
    else {
        cout << -1 << endl;
    }

    return 0;
}

Python과 C++ 모두 같은 알고리즘으로 풀어서 시간은 꽤 오래걸렸다.