[SWEA] 파이썬 5215. 햄버거 다이어트 | DFS

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

SW Expert Academy

 

 

문제 해결 포인트

- 이진트리를 생각하면서 모든 재료를 넣는 경우와 넣지 않는 경우를 나눠서 탐색

- 현재까지 계산한 값이 최대 칼로리를 넘어가면 해당 경우에 대해서 더이상 탐색하지 않아도 됨

- BFS로도 구현할 수 있지만 가지치기를 할 수 있으므로 BFS보다 DFS가 더 이상적이다.

 

 

작성 코드

 

def dfs(vertex, sat, cal):
    global result
    if cal <= L:  # L 주의(1000 아님)
        result = sat if sat > result else result  # 만족도가 크다면 갱신
        if vertex < N:  # 모든 재료 사용 안 했으면
            dfs(vertex+1, sat + igr[vertex][0], cal + igr[vertex][1]) # 해당 재료 넣음
            dfs(vertex+1, sat, cal)  # 해당 재료 안 넣음

for test in range(1, int(input())+1):
    result = 0
    N, L = list(map(int, input().split()))  # 재료 개수, 칼로리 제한
    igr = [list(map(int, input().split())) for _ in range(N)]  # 재료 별 만족도, 칼로리

    dfs(0, 0, 0)

    print("#{} {}".format(test, result))

 

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

 

---

REFERENCE

https://mungto.tistory.com/170