[Python] 백준 12865 - 평범한 배낭 문제 풀이

Overview

BOJ 12865번 평범한 배낭 Python 문제 풀이
분류: Dynamic Programming (동적계획법)

---

문제 페이지

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

---

풀이 코드

from sys import stdin


def main():
    n, k = map(int, stdin.readline().split())
    items = [list(map(int, stdin.readline().split())) for _ in range(n)]

    dp = [[0] * (k + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, k + 1):
            if items[i - 1][0] <= j:
                dp[i][j] = max(dp[i - 1][j - items[i - 1][0]] + items[i - 1][1],
                               dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]

    print(dp[n][k])


if __name__ == "__main__":
    main()

다이나믹 프로그래밍을 이용한 Knapsack 문제이다.