[SWEA/D3] 5215 : 햄버거 다이어트 python

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AWT-lPB6dHUDFAVT&categoryId=AWT-lPB6dHUDFAVT&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

SW Expert Academy

 

 

아이디어

• 맛에 대한 점수와 칼로리를 튜플로 리스트에 저장한다.
• 가장 높은 점수를 저장할 전역변수 answer를 생성한다.
• 인덱스, 누적된 점수, 누적된 칼로리를 매개변수로 하는 함수 dfs를 구현한다.
  • 현재 누적된 칼로리가 L보다 크면 더이상 재료를 넣을 수 없으므로 return한다.
  • 현재 누적된 점수가 answer(기존점수)보다 크면 answer를 갱신한다.
  • 같은 재료를 중복해서 사용할 수 없으니 인덱스==N이라면 return한다.
  • 재료를 선택하는 경우와 선택하지 않는 경우를 나눠서 dfs 탐색을 한다.

 

코드

def dfs(idx, score, kcal):
    global answer
    if kcal>L:
        return
    if answer<score:
        answer = score
    if idx == N:
        return
    dfs(idx+1,score+data[idx][0],kcal+data[idx][1])
    dfs(idx+1,score,kcal)
 
T = int(input())
for test_case in range(1, T + 1):
    N,L=map(int,input().split())
    data = []
    answer =0
    for i in range(N):
        score, kcal = map(int,input().split())
        data.append((score,kcal))
     
    dfs(0,0,0)
     
    print('#{} {}'.format(test_case,answer))

 

 

후기

• 문제를 처음 봤을 때 냅색 알고리즘이 떠올랐다. 그렇지만 복습을 성실히 하지 않아서...풀이를 떠올릴 수 없었다.
• 완전탐색으로 풀기엔 시간초과가 나올 게 분명해서 가지치기를 어떻게하나 하다가 결국 다른 사람들의 풀이를 참고했다.
• 2차원 리스트에서 상하좌우로 탐색하는 BFS/DFS 문제를 보면 풀이가 딱 떠오르는데, 아직 이런 유형의 문제를 보고 DFS로 풀면 되겠다는 생각은 들지 않는다.
• 더 다양한 유형을 많이 풀어보는 수밖에 없는 듯하다.