백준 12865 평범한 배낭 파이썬

백준 12865 평범한 배낭 풀이

실패코드

import sys
input = lambda: sys.stdin.readline().rstrip()

n, k = map(int, input().split())

arr = []

for _ in range(n):
    w, v = map(int, input().split())
    arr.append([w, v])

# 무게 k를 넘지 않으면서 가치가 최대여야 한다.
# dp로 해결

dp = [0 for _ in range(n+1)]
ans = 0
for i in range(n):
    dp[i] = arr[i][1]

for i in range(n):
    for j in range(i+1, n):
        if arr[i][0] + arr[j][0] <= k:
            ans = max(ans, dp[i] + dp[j])

print(ans)

정답코드

import sys
input = lambda: sys.stdin.readline().rstrip()

n, k = [int(x) for x in input().split()]
table = [0] * (k+1)
for _ in range(n):
    w, v = [int(x) for x in input().split()]
    if w > k:
        continue
    for j in range(k, 0, -1):
        if j + w <= k and table[j] != 0:
            table[j+w] = max(table[j+w], table[j] + v)
    table[w] = max(table[w], v)
print(max(table))

접근방식

단순히 기준 무게를 넘지 않는 선에서 가치를 최대로 만들도록

2중 for문을 사용했는데 테스트 케이스 하나를 제외하고 오류인 코드였습니다.

문제에 대한 해답을 얻고자 찾아보던 도중, 냅색(Knapsack) 알고리즘에 대해

알게 되었고, 배낭 문제를 다룰 수 있는 알고리즘이었습니다.

https://reakwon.tistory.com/34
https://roamingman.tistory.com/62

위 두 블로그를 참고하면서 냅색 알고리즘을 처음 접하게 되었고,

해당 블로그에는 영상으로 된 상세한 풀이과정이 있어서 매우 유용했습니다.

해당 문제는 골드 5레벨의 DP, 냅색 알고리즘 문제였습니다.

처음 접하게 된 알고리즘이어서 이해하는 데 꽤 많은 시간이 걸렸지만

앞으로 반복해서 공부해야 할 필요가 있습니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady