SWEA 5215 햄버거 다이어트 (Python, DFS)

5215 햄버거 다이어트 문제 바로가기

문제 접근

문제를 처음 보고 과거에 알고리즘 강의에서 배운 0/1knapsack이 생각났다. 그래서 그 방법으로 풀어도 되겠다고 생각했는데, 오랜만에 하려고 하다보니 생각도 잘 안나고 쉽지 않았다...... 이래서 복습이 중요한건데ㅜ
그래서 DFS로 완전탐색하여 풀었다.
중요한건 선택을 하느냐 안하느냐를 처리하는 부분이었는데 DFS로 풀게되면 이 부분을 쉽게 처리해줄 수 있었다.

문제 풀이

아래의 코드를 보면 i+1로 다음 인덱스로 넘겨줌과 동시에 현재 인덱스의 재료를 선택했다면 맛과 칼로리에 더해주고 선택하지 않았다면 인덱스만 증가시켜준다. 이를 통해서 선택하는 부분을 처리했다.

dfs(i+1, taste + s[i], kcal + k[i])
dfs(i+1, taste, kcal)

제출 코드

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N, L = map(int, input().split())
    s = []
    k = []
    def dfs(i, taste, kcal):
        global max_taste
        if kcal>L: # 칼로리 초과
            return
        if taste > max_taste: # 최대 칼로리 저장
            max_taste = taste
        if i==N: # 끝
            return
        dfs(i+1, taste + s[i], kcal + k[i]) # 현재 재료 선택
        dfs(i+1, taste, kcal) # 현재 재료 미선택
    for _ in range(N):
        score, kcal = map(int, input().split())
        s.append(score)
        k.append(kcal)
    max_taste = 0
    dfs(0,0,0)
    print(f'#{test_case} {max_taste}')