[백준] 12865번 평범한 배낭

• 링크

n, k = map(int, input().split())
# 점화식을 위해 메모이제이션 할 리스트를 생성
dp = [[0] * (k+1) for _ in range((n+1))]


for i in range(1, n+1):
    weight, value = map(int, input().split())
    for j in range(1, k+1):
        # 만약 순회하는 값이 무게보다 작다면 
        if j < weight:
            # 값을 그대로 상속받는다. 이유로는 해당 kg에 해당하는 짐이 되지 않기 때문이다.(1kg에 3kg에 해당하는 짐을 넣을 수 없기 때문이다.)
            dp[i][j] = dp[i-1][j]
        else:
        # 순회하는 값이 받은 값보다 크거나 같다면 해당 무게에 해당하는 최대 가치를 담는다.
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight]+value)
print(dp[n][k])

각 무게에 따라 최적의 가치를 가지는 상황을 만들어 내야 하는 문제임을 알고 있었다.

재귀호출을 통해 풀어야 하나 고민을 해 보았지만 DP 문제임을 자각 한 상태에서 재귀를 호출하여
풀기를 망설였고 재귀로 풀어보려 하였으나 머리가 복잡해져 실패하였다.

결국 코드를 찾아보게 되었으며 아직도 완전하게 이해가 가지 않아 지속적으로 풀어보며 원리를 이해해야 할 것 같다.

백 트래킹과 DP는 코딩테스트에 자주 출제되는 문제라고 알고 있어, 꾸준히 복기하며 코테를준비해보도록 하겠습니다.