[Python] SWEA 5215번 햄버거 다이어트

문제

SW Expert Academy

문제 풀이

• 탐색하려는 최대 맛의 합을 전역변수로 놓고 dfs탐색을 진행하여, 인덱스 별 재료를 넣는 경우와, 넣지 않는 경우로 나눠서 탐색한다.
• dfs 탐색을 하면서, 최대 맛 값을 계산하기 위해 맛을 계산하는 임시 변수에 인덱스 별 맛 값을 더한 후, 그 값이 최대 맛 값을 저장해놓은 max_taste값보다 크다면 max_taste값을 갱신한다.
  • 칼로리 값도 위와 같이 계산한 후, 재귀함수를 실행할 때 총 칼로리의 합이 제한 되어있는 칼로리 값보다 더 크다면 호출을 종료한다.
• 그 후 마지막인덱스까지 돌았다면 종료한다.
  • 마지막 인덱스의 칼로리와 맛을 계산하면 종료되는 인덱스의 값이 n - 1이 아닌 n이다.
• 그 후 탐색한 최대 맛 값(max_taste) 값을 형식에 맞게 출력한다.

코드

def make_hamburger(index, taste, kcal):
    global max_taste

    # 칼로리 넘으면 종료
    if kcal > l:
        return
    # 칼로리 넘지 않으면 최대 맛 값 갱신
    if max_taste < taste:
        max_taste = taste

    # 인덱스 다 돌면 종료
    if index == n:
        return

    tmp_taste, tmp_kcal = data[index]
    # 재료 추가하는 경우
    make_hamburger(index + 1, tmp_taste + taste, tmp_kcal + kcal)
    # 재료 추가하지 않는 경우
    make_hamburger(index + 1, taste, kcal)

t = int(input())
for tc in range(t):
    n, l = map(int,input().split())
    data = [list(map(int,input().split())) for _ in range(n)]
    # 최대 맛 값
    max_taste = 0
    make_hamburger(0,0,0)
    print(f'#{tc + 1}',max_taste)