[SWEA] 5215.햄버거 다이어트/Python - D3

❓문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT

SW Expert Academy

성능 요약

메모리: 57,264 KB, 시간: 590 ms, 코드길이: 441 Bytes

✍🏻풀이

정해진 칼로리를 넘기지 않으면서 가장 점수가 높은 햄버거를 찾는 문제이다.
정해진 칼로리가 1000일 때, 주어진 재료들로 1000을 넘기지 않으면서 가장 점수가 높은 햄버거를 만들어야 한다.
주어진 재료들의 점수와 칼로리가 각각 (100, 200), (300, 500), (250, 300), (500, 1000), (400, 400)이라고 한다면
이때 가장 높은 점수는 750이 되며 칼로리는 900으로 정해진 칼로리를 넘기지 않는다.
첫번째 재료부터 살펴본다. 혹은 두번째 재료부터 점수를 계산할 수 있다. 즉, 현재 점수에서 지금 위치의 재료를 사용하지 않고 다음 위치의 재료를 사용하면서 가장 높은 점수를 만드는 것이다.

💻코드

t = int(input())

def dfs(s, c, d):
    global ms
    if c > l:
        return 
    ms = max(ms, s)
    if d == n:
        return

    dfs(s + scores[d], c + calories[d], d+1)
    dfs(s, c, d+1)


for i in range(1, t + 1):
    n, l = map(int, input().split())
    scores = [0] * n
    calories = [0] * n

    for j in range(n):
        scores[j], calories[j] = map(int, input().split())

    ms = 0
    dfs(0, 0, 0)


    print(f"#{i} {ms}")

📍후기

처음에는 napsack문제처럼 dp인 줄 알고 시도했는데 아무리 생각해도 dp로 어떻게 해야 할지 감이 안 잡혔다. 전에도 비슷한 유형의 문제도 처음에는 dp인가 했는데 그 문제도 결국 dfs 문제였던 것 같다. 알고리즘 문제는 왜 풀어도풀어도 감이 안 잡히는 것 같지..