[swea] 5215번: 햄버거 다이어트 - 파이썬(python)

재료리스트, 칼로리리스트의 0~n-1 까지의 인덱스에 재료점수와 재료의 칼로리를 저장해둔다.

그런 다음 i번째 재료를 추가할지, 추가하지 않을지의 여부에 따라 DFS 를 진행해간다.

i가 n 이라면, 1~n까지의 재료에 대해 모든 선택을 완료한 것이므로, DFS 를 종료한다.

 

* 지금까지 구한 점수 + 현재 인덱스부터 끝 인덱스까지 점수를 모두 더한 값이 현재 max_score 이하라면, 굳이 검사를 하지 않아도 최댓값이 갱신되지 않으므로 바로 return 할 수 있다. 

이는 시간을 줄일 수 있는 아주 좋은 방법이다.

 

 

 

나의 풀이

def dfs(i, total, calorie):
    global max_score
    if i == n:
        max_score = max(max_score, total)
        return
    # 앞으로 더할 수 있는 최댓값이 max_score 보다 작다면 검사할 필요X
    if total + sum(s[i:]) <= max_score : 
        return
    if calorie + c[i] <= kcal:
        dfs(i+1, total+s[i], calorie + c[i])
    dfs(i+1, total, calorie)

T = int(input())
answer = []
for t in range(1, T+1):
    n, kcal = map(int, input().split())
    s = []
    c = []
    for _ in range(n):
        a, b = map(int, input().split())
        s.append(a)
        c.append(b)
    max_score = 0
    dfs(0, 0, 0)
    answer.append(f'#{t} {max_score}')

print(*answer, sep='\n')