[백준] 19942. 다이어트

# 문제 설명

 

# 입출력 예시

입력	출력
6 100 70 90 10 30 55 10 8 100 60 10 10 2 70 10 80 50 0 50 40 30 30 8 60 60 10 70 2 120 20 70 50 4 4	134 2 4 6

 

# 코드 풀이

n = int(input())
mp,mf,ms,mv = list(map(int, input().split(' ')))
diets = [list(map(int, input().split(' '))) for _ in  range(n)]

costs = []
cost_min = 9999
def dfs(path, rest):
    global costs, cost_min
    sum_x = sum([diets[i][4] for i in path])
    if len([x for x in rest if x > 0]) == 0:
        if sum_x < cost_min :
            costs = path
        cost_min = min(sum_x, cost_min)   
        return
    if len(path) == n:
        return
    if sum_x > cost_min:
        return
        
    for i in range(n):
        if i not in path:
            dfs(path[:]+[i], [max(0, y-x) for x, y in zip(diets[i], rest)])

dfs([], [mp,mf,ms,mv])

print(cost_min)
for x in costs:
    print(x, end=' ')

 

# 핵심 포인트

• 비용의 최저 값인 cost_min을 함수에서 계속 업데이트 하므로, global로 지정하여 사용한다.
• 최저 값을 찾았더라도 해당 경우에 대해 한 번은 함수를 시작하므로, 모든 노드를 돌거나 최저값을 가질 것 같지 않은 경우 return한다.