[BOJ/백준] 19942 다이어트 파이썬

문제 링크 : https://www.acmicpc.net/problem/19942

19942번: 다이어트

브루트포스 문제이다.

재귀로도 할수 있겠지만 파이썬은 이미 아주 훌륭한 조합를 제공한다.

1개,2개,n개까지 뽑는 조합을 다 만들어서 조건을 만족시키고 합이 최소가 되는 것을 찾아서 출력했다.

그리고 중간이 합이 같다면 사전순으로 앞선것이 와야한다.

그래서 두개를 하나의 튜플로 만들어 정렬하고 앞에것을 저장했다.

 

from sys import stdin
from itertools import combinations

input = stdin.readline

n = int(input())
mp,mf,ms,mv = map(int, input().split())

board = [[]]
for _ in range(n):
    p,f,s,v,c = map(int, input().split())
    board.append((p,f,s,v,c))

def solv():
    answer_c = 9875643210
    answer = None
    for cnt in range(1,n+1):
        for comb in combinations(range(1,n+1),cnt):
            tp=tf=ts=tv=tc=0
            for target in comb:
                tp += board[target][0]
                tf += board[target][1]
                ts += board[target][2]
                tv += board[target][3]
                tc += board[target][4]

            if tp >= mp and tf >= mf and ts >= ms and tv >= mv:
                if answer_c > tc:
                    answer_c = tc
                    answer = comb
                elif answer_c == tc:
                    answer = sorted((answer,comb))[0]
    if answer_c == 9875643210:
        print(-1)
    else:
        print(answer_c)
        print(*answer)

solv()