[백준] 12865 : 평범한 배낭

문제

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

풀이

1차원 배열

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
stuff = []
for _ in range(n):
    stuff.append(list(map(int, input().split())))
dp = [0 for _ in range(k+1)] # k가 7일 때 dp는 0 1 2 3 4 5 6 7 되도록 k+1까지 만들어줌

stuff.sort()

for weight, value in stuff:
    # 뒤에서부터 채워야 짐이 여러번 들어가지 않음!
    # 앞에서부터 채우면 짐이 여러번 중복됨!
    for j in range(len(dp)-1, -1, -1): # dp의 인덱스를 모두 가져올 수 있음 (인덱스가 곧 무게)
        if j >= weight: # 무게의 총합보다 현재 무게가 이하일 때만 만들어줄 수 있음
            dp[j] = max(dp[j], dp[j-weight] + value)
print(dp[-1])

2차원 배열

import sys
input = sys.stdin.readline

n, k = map(int, input().split()) # n 물품 수 k 최대 무게
stuff = [[0,0]]
for _ in range(n):
    stuff.append(list(map(int, input().split()))) # stuff[0][0] = 무게, stuff[0][1] = 가치
dp = [[0 for _ in range(k+1)] for _ in range(n+1)] # dp 테이블 

for i in range(1, n+1):
    for j in range(1, k+1):
        weight = stuff[i][0] 
        value = stuff[i][1]
        
        if weight > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(value + dp[i-1][j-weight], dp[i-1][j]) # i가 행으로 i-1 아직 내꺼 안 넣었을 때 j는 무게
# print(dp)
print(dp[n][k])