[문제 풀이] 백준 12865

해결 과정

처음 봤을 때 정확하게 이해 못했다가, 각 잡고 천천히 이해해봤다.

dp[N][K] ➡️ N번째 물건까지 쓰고, 수용 가능한 무게 K라고 할 때의 최대 가치.

나의 풀이

# knapsack 알고리즘
def solution(n, k, objects):
    dp = [[0] * (k+1) for i in range(n+1)]
    objs = [[0, 0]] + objects
    
    for i in range(1, n + 1):
        for j in range(1, k + 1):
            if j >= objs[i][0]:
                dp[i][j] = max(objs[i][1] + dp[i-1][j-objs[i][0]], dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]

    return dp[n][k]

n, k = map(int, input().split())
objects = [list(map(int, input().split())) for i in range(n)]

print(solution(n, k, objects))

# print(solution(4, 7, [[6, 13], [4, 8], [3, 6], [5, 12]]))

다른 풀이

이 분 글을 참고했다. 

#159 백준 파이썬 [12865] 평범한 배낭 - 냅색 알고리즘

IDEA