[SWEA]햄버거 다이어트 - 5215 (D3)

시간 제한	메모리 제한
16 초	힙 정적 메모리: 256 MB / 스택 메모리 1MB

문제

평소 햄버거를 좋아하던 민기는 최근 부쩍 늘어난 살 때문에 걱정이 많다.

그렇다고 햄버거를 포기할 수 없었던 민기는 햄버거의 맛은 최대한 유지하면서 정해진 칼로리를 넘지 않는 햄버거를 주문하여 먹으려고 한다.

민기가 주로 이용하는 햄버거 가게에서는 고객이 원하는 조합으로 햄버거를 만들어서 준다.

하지만 재료는 미리 만들어서 준비해놓기 때문에 조합에 들어가는 재료를 잘라서 조합해주지는 않고, 재료를 선택하면 준비해놓은 재료를 그대로 사용하여 조합해준다.

민기는 이 가게에서 자신이 먹었던 햄버거의 재료에 대한 맛을 자신의 오랜 경험을 통해 점수를 매겨놓았다.

민기의 햄버거 재료에 대한 점수와 가게에서 제공하는 재료에 대한 칼로리가 주어졌을 때,

민기가 좋아하는 햄버거를 먹으면서도 다이어트에 성공할 수 있도록 정해진 칼로리 이하의 조합 중에서 민기가 가장 선호하는 햄버거를 조합해주는 프로그램을 만들어보자.

(단 여러 재료를 조합하였을 햄버거의 선호도는 조합된 재료들의 맛에 대한 점수의 합으로 결정되고, 같은 재료를 여러 번 사용할 수 없으며, 햄버거의 조합의 제한은 칼로리를 제외하고는 없다.)

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 재료의 수, 제한 칼로리를 나타내는 N, L(1 ≤ N ≤ 20, 1 ≤ L ≤ 104)가 공백으로 구분되어 주어진다.

다음 N개의 줄에는 재료에 대한 민기의 맛에 대한 점수와 칼로리를 나타내는 Ti, Ki(1 ≤ $T_i$ ≤ 103, 1 ≤ Ki ≤ 103)가 공백으로 구분되어 주어진다.

출력

각 줄마다 “#T” (T는 테스트 케이스 번호)를 출력한 뒤, 주어진 제한 칼로리 이하의 조합중에서 가장 맛에 대한 점수가 높은 햄버거의 점수를 출력한다.

풀이

DFS를 활용한 풀이

가장 먼저 떠오른 방식은 DFS를 활용한 방식이다. 햄버거 재료를 하나씩 사용하며(재료 수를 하나씩 줄여가며) 재귀를 반복한다. 사용한 재료에 맞게 칼로리와 점수를 더해서 다음 재귀의 매개변수로 넘겨준다. 그리고 매 시행마다 점수가 최대인지 확인하고 기록해준다.

하지만 현재 재료까지의 칼로리 합이 제한 칼로리보다 높다면 더 이상 탐색할 필요가 없으므로 넘어간다.

코드

test_case = int(input())


# 제한 칼로리 내에서 최대의 맛
def search_best(hamburgers, sum_cal=0, sum_score=0):
    global max_score
    max_score = max(max_score, sum_score)

    for i, (score, cal) in enumerate(hamburgers):
        if sum_cal + cal > l:
            continue
        search_best(hamburgers[i + 1:], sum_cal + cal, sum_score + score)


for t in range(test_case):
    n, l = map(int, input().split())

    hamburgers = [list(map(int, input().split())) for _ in range(n)]

    max_score = 0

    search_best(hamburgers)

    print(f"#{t + 1} {max_score}")

DP를 활용한 풀이

이 문제를 다시 생각해보면 재료를 고르거나(1) 안고르면서(0) 주어진 칼로리(용량) 내에서 최대의 점수(이득)을 얻는 것이 목적이므로, 0-1 배낭 문제와 동일하다.

이에 이전까지의 맛 점수의 최대치를 활용하여, 칼로리 제한 l에서 내려가며 가장 높은 점수를 계산한다. 말로 하니 어려우니 아래 예시를 보자.

DP를 위한 점화식은 다음과 같디.

dp = [0] * (l + 1)
...
dp[j] = max(dp[j], dp[j - cal] + score)

이 점화식을 아래 예시 입력으로 연산을 진행해보자.

1
5 1000
100 200
300 500
250 300
500 1000
400 400

첫 입력은 점수 100, 칼로리 200의 재료이다. (편의상 100 단위로 인덱스를 표시했지만 실제로는 1단위이다.)

score	cal
100	200

$j$	1000	900	800	700	600	500	400	300	200	100	0
$j-cal$	800	700	600	500	400	300	200	100	0	-	-
$DP_{before}$	0	0	0	0	0	0	0	0	0	0	0
$DP_{next}$	100	100	100	100	100	100	100	100	100	0	0

점화식에 따라 현재 인덱스의 (dp 배열 값)과 (j - cal 인덱스 값 + 현재 score 값) 중 큰 값을 취한다.

즉, 지금까지 저장한 현재 위치의 칼로리 j와 (score + j-cal) 칼로리로 만들 수 있는 맛 점수를 비교하는 것이다.

한 스탭 더 진행해보자.

score	cal
300	500

$j$	1000	900	800	700	600	500	400	300	200	100	0
$j-cal$	500	400	300	200	100	0	-	-	-	-	-
$DP_{before}$	100	100	100	100	100	100	100	100	100	0	0
$DP_{next}$	400	400	400	400	300	300	100	100	100	0	0

j가 1000 ~ 700일 때까지는 기존 DP 배열의 인덱스 500 ~ 200까지의 값과 합하여 기존 값과 비교한다. 비교 결과 새로운 값이 더 크기 때문에 400(100 + 300)으로 갱신한다. j가 600 ~ 500일 때도 마찬가지로 진행하지만 기존 값이 0이기 때문에 300(0 + 300)으로 갱신한다.

이후에도 같은 과정으로 진행한다.

score	cal
250	300

$j$	1000	900	800	700	600	500	400	300	200	100	0
$j-cal$	700	600	500	400	300	200	100	0	-	-	-
$DP_{before}$	400	400	400	400	300	300	100	100	100	0	0
$DP_{next}$	650	550	550	400	350	350	250	250	100	0	0

score	cal
500	1000

$j$	1000	900	800	700	600	500	400	300	200	100	0
$j-cal$	0	-	-	-	-	-	-	-	-	-	-
$DP_{before}$	650	550	550	400	350	350	250	250	100	0	0
$DP_{next}$	650	550	550	400	350	350	250	250	100	0	0

score	cal
400	400

$j$	1000	900	800	700	600	500	400	300	200	100	0
$j-cal$	600	500	400	300	200	100	0	-	-	-	-
$DP_{before}$	650	550	550	400	350	350	250	250	100	0	0
$DP_{next}$	750	750	650	650	500	400	400	250	100	0	0

마지막 시행이 끝난 후 DP 배열에서 최대값을 출력한다.

코드

test_case = int(input())

for t in range(test_case):
    n, l = map(int, input().split())

    hamburgers = [list(map(int, input().split())) for _ in range(n)]

    dp = [0] * (l + 1)

    for score, cal in hamburgers:
        for j in range(l, cal - 1, -1):
            dp[j] = max(dp[j], dp[j - cal] + score)

    max_score = max(dp)

    print(f"#{t + 1} {max_score}")