백준 - 평범한 배낭(12865)

그간 알고리즘 문제를 풀었는데

한번도 정리한적이 없다.

양이 정말 많은데..... 차근차근 정리를 해본다. 복습할겸

 

 

 

로직은 dp로 풀었다.

dp의 근본 문제같은 느낌?? 이었다.

 

n,k = map(int, input().split())
wv = [[0,0]]
for i in range(n):
    wv.append(list(map(int, input().split())))
dp = [[0]*(k+1) for _ in range(n+1)]
for i in range(n+1):
    for j in range(1,k+1):
        w = wv[i][0]
        v = wv[i][1]
        if j < w: dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-w]+v)
print(dp[n][k])