[DP] BOJ 12865 평범한 배낭

문제

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

12865번: 평범한 배낭

 

풀이

실버까지의 DP는 값을 직접적으로 이용했지만

골드부터는 수치적인 제한이 생기면서 유형이 바뀐듯하다.

처음엔 물건들로 2차원 배열을 생각했으나 물건을 선택하는 것과 하지 않는 것을 분리하지 못했다.

 

1. row는 주어지는 물건의 개수 N col은 0부터 가방의 제한 무제 K의 2차원 리스트를 만든다.

2. 현재 물건을 넣을 수 있을 때,이전 물건을 선택 했을 때 현재 물건을 넣는 경우와 현재 물건을 넣지 않는 경우로 생각한다.

3. 모든 물건을 2번 처럼 살핀다.

 

코드

import sys

N, K = map(int,sys.stdin.readline().split())

bag_list = []

for _ in range(N):
    bag_list.append(list(map(int,sys.stdin.readline().split())))

d = [[0] * (K+1) for _ in range(N+1)]

for i in range(N):
    w = bag_list[i][0]
    v = bag_list[i][1]
    for j in range(K+1):
        if j >= w:
            d[i+1][j] = max(d[i][j], d[i][j-w] + v)
        else:
            d[i+1][j] = d[i][j]
 
print(d[N][K])