728x90
https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
[백준알고리즘] 12865번: 평범한 배낭 -Python
[백준알고리즘] 12865번: 평범한 배낭 -Python https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진..
suri78.tistory.com
이 형님 설명이 아주 친절하다. 나도 이 분의 표와 설명을 안 들었으면 이해 못 하고 밤을 샜을것같다..
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
dp = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(1, n + 1): # 물건을 한개씩 순회
w, v = map(int, input().split())
for j in range(1, k + 1):
if j < w: # 만약 이번 물건을 넣을 수 없다면 이전 물건까지 넣었던것의 value 값을 그대로 계승
dp[i][j] = dp[i - 1][j]
else: # 만약 이번 물건을 넣을 수 있다면
# 이전 물건까지 넣었던것의 v 와 이번 물건을 넣었을떄의 v 중 dp가 큰 값으로 갱신
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
print(dp[n][k])
|
cs |
728x90
'PS > 백준' 카테고리의 다른 글
| [백준 1300번] K번째 수 (파이썬/python) (0) | 2021.06.16 |
|---|---|
| [백준 12015번] 가장 긴 증가하는 부분 수열 2 (파이썬/python) (0) | 2021.06.16 |
| [백준 2110번 ] 공유기 설치 (파이썬/python) (0) | 2021.06.15 |
| [백준 11279번] 최대 힙 (파이썬/python) (0) | 2021.06.15 |
| [백준 2606번] 바이러스 (파이썬/python) (0) | 2021.06.15 |
