12865 - 평범한 배낭

 

---

 

문제

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

12865번: 평범한 배낭

 

풀이

https://www.youtube.com/watch?v=rhda6lR5kyQ&t=704&ab_channel=%EC%BD%94%EB%93%9C%EC%97%86%EB%8A%94%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D 

* 위 영상을 참고했음

 

 

코드

n, k = map(int, input().split())

board = [ [0] * (k+1) for _ in range(n+1) ]
bags = [(0, 0)]
for _ in range(n):
    w, v = map(int, input().split())
    bags.append((w, v))

for i in range(1, n+1):
    for j in range(1, k+1):
        w = bags[i][0]
        v = bags[i][1]

        # 무게가 넘는다면
        if j < w:
            board[i][j] = board[i-1][j]
        # 그렇지 않다면
        else:
            board[i][j] = max(board[i-1][j], board[i-1][j - w] + v)

print(board[n][k])

 

후기

 

DP문제는 '작은 문제로 나누는 것' 부터 천천히 시작하면, 접근이 가능한 거 같다.

또한 이러한 문제와 비슷한 문제가 많기에.. 최대한 익숙해지면서 풀 수 있도록 노력해야겠다.