7579번 - 앱 / gold 3 / DP(냅색 알고리즘)

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

7579번: 앱

'''
7579번 - 앱 / gold 3 / DP(냅색 알고리즘)
'''
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
memory = [0] + list(map(int, input().split()))
cost = [0] + list(map(int, input().split()))
dp = [[0 for _ in range(sum(cost) + 1)] for _ in range(n + 1)]
min_cost = sum(cost)

for row in range(1, n + 1):
    byte = memory[row]
    expense = cost[row]
    for col in range(1, sum(cost) + 1):
        if col < expense:
            dp[row][col] = dp[row - 1][col]
        else:
            dp[row][col] = max(byte + dp[row - 1][col - expense],
                               dp[row - 1][col])
        if dp[row][col] >= m:
            min_cost = min(min_cost, col)

if m == 0:
    print(0)
else:
    print(min_cost)

 

예제 1번 dp 리스트 예시

col 행 : 전체 sum(cost) = 15 길이 까지

row 열 : n = 5 까지

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	30	30	30	30	30	30	30	30	30	30	30	30	30
2	0	10	10	40	40	40	40	40	40	40	40	40	40	40	40	40
3	0	10	10	40	40	40	40	60	60	60	60	60	60	60	60	60
4	0	10	10	40	40	40	60	60	75	75	75	95	95	95	95	95
5	0	10	10	40	40	50	60	80	80	80	100	100	115	115	115	135

• row 가 1일때, byte = 30, expense = 3이므로
  • col = 3~15 : 30(byte) + 0(dp[0][col])
• row 가 2일때, byte = 10, expense = 0 이므로
  • col = 1 : 10(byte) + 0(dp[1][1]) = 10
  • col = 2 : 10(byte) + 0(dp[1][2]) = 10
  • col = 3~15 : 10(byte) + 30(dp[1][col-expense]) = 40
• (생략)

 

대략 설명

- 해당 표와 같이 dp[row][col]를 순차적으로 확인한다.

- row 는 1~n 까지 반복문 돌기 (이중 for 문 / col 은 1~15까지 반복문 돌기)

 

• 해당 dp의 값 넣기 이해하기
  • 만일 row = 2 , col = 6이라면
  • memory[1] memory[2], expense[1], expense[2]만 있는 상황에서 / row = 2
  • 최대 비용이 6까지 쓸 수 있는 상황에서 메모리의 최대값을 dp에 넣기 / col = 6