[다이나믹 프로그래밍] 백준 7579번 : 앱 / 골드 3

https://www.acmicpc.net/problem/7579

7579번: 앱

import sys
input = sys.stdin.readline
n, capacity = map(int, input().split())
byte = list(map(int, input().split()))
cost = list(map(int, input().split()))

max_cost = sum(cost)
dp = [[0]*(max_cost+1) for _ in range(n+1)]

for i in range(n + 1):
    for j in range(max_cost + 1):
        if i == 0:
            dp[i][j] = 0
        elif cost[i-1] <= j:
            dp[i][j] = max(dp[i-1][j], byte[i-1] + dp[i-1][j - cost[i-1]])
        else:
            dp[i][j] = dp[i-1][j]

for j in range(max_cost + 1):
    for i in range(n + 1):
        if dp[i][j] >= capacity:
            print(j)
            quit()

너무 풀기 어려워서 힌트를 많이 얻었다.

일단 알고리즘 분류- 배낭문제라서 배낭 문제를 참고하였고

그래도 여전히 모르겠어서 구글링을 통해 사람들이 테이블을 어떤 식으로 만드는 지 살펴봤다.

 

테이블의 가로는 cost, 세로는 n이었고

풀이 방식은 특정 cost, n에 대해 확보할 수 있는 메모리의 최댓값을 찾는 것이었다.

핵심 점화식은 다음과 같다.

dp[i][j] = max(dp[i-1][j], byte[i-1] + dp[i-1][j - cost[i-1]])

dp[i][j]는 두개 중 큰 값을 취하는데

dp[i-1][j]는 테이블에서 바로 위에 있는 값, 즉 i-1번째 앱이 추가되지 않았을 때의 값이고

byte[i-1] + dp[i-1][j-cost[i-1]])는 i-1번째 앱이 추가되었다고 하였을 때 확보가능한 메모리의 최댓값이다. 

 

이때 byte[i-1]가 추가된 앱에 의한 추가 메모리값이고, 여기에 이 앱의 현재 칼럼의 cost에서 앱의 cost를 뺀, 즉 여분의 cost에 해당하는 j-cost[i-1] 을 이용하여 윗 행에서 dp[i-1][j-cost[i-1]]을 가져온다.

 

복습이 많이 필요할 것 같다.. 아 어려워