[SWEA/DFS-BFS] 5215[D3]: 햄버거 다이어트 - 파이썬

문제

SWEA-5215. 햄버거 다이어트

SW Expert Academy

 

풀이

DFS를 이용해 풀이하였음.

햄버거 재료수(N), 넘지 말아야 하는 칼로리수(L)을 입력받고

리스트를 생성하고 재료의 맛과 칼로리를 저장한 후 

 

재료가 저장된 리스트의 인덱스 0 부터 끝까지 깊이 우선 탐색함.

탐색할때마다 칼로리가 넘어가면 탐색을 수행하지 않고

기존에 저장된 최대 맛보다 크면 갱신 과정을 거침

 

재료를 썼을 때, 안 썼을 때 를 각각 탐색함.

def dfs(index, sTaste, sKcal):
    global maxTaste
    
    # 총 칼로리를 넘으면 리턴
    if sKcal > L:
        return
        
    # taste의 합이 제일큰 taste 합보다 크면 갱신
    if maxTaste < sTaste:
        maxTaste = sTaste
        
    # 햄버거 재료 데이터를 다 돌면 리턴
    if index == N:
        return
        
    # index 파라미터를 통해 taste, kcal 대입
    taste, kcal = data[index]
    
    # 햄버거 재료 리스트에서 재료를 사용했을 때
    dfs(index + 1, sTaste + taste, sKcal + kcal)
    # 햄버거 재료 리스트에서 재료를 사용하지 않았을 때
    dfs(index + 1, sTaste, sKcal)

t = int(input())
for tc in range(1, t+1):
    # N: 햄버거 재료 수, L: 넘지 말아야 하는 칼로리 양
    N, L = map(int, input().split())
    
    # 햄버거와 칼로리 리스트 저장
    data = [list(map(int, input().split())) for _ in range(N)]
    
    maxTaste = 0
    dfs(0, 0, 0)
    
    print("#{} {}".format(tc, maxTaste))