[HackerRank] Knapsack

def unboundedKnapsack(k, arr):
    # Write your code here
    
    row = len(arr)
    col = k
    
    dp = [[0]*(k+1) for _ in range(row+1)]
    
    for i in range(1,row+1):
        dp[i][0] = 1
    
    for i in range(1,row+1):
        for j in range(1,col+1):
            if j >= arr[i-1]: 
                dp[i][j] = dp[i-1][j] + dp[i][j-arr[i-1]]
            else:
                dp[i][j] = dp[i-1][j]
    
    for i in range(col,-1,-1):
        if dp[row][i] != 0:
            return i

이번 문제는 주어진 배열(arr)의 원소들을 가지고 만들 수 있는 타겟 값(k)을 초과하지 않으면서 가장 가까운 값을 찾는 문제이다. 해당 문제를 보자마자 떠오른 것은 0-1 배낭문제였는데, 0-1 배낭문제와는 다르게 짐이 무한개 있다는 가정이 있다는 차이가 있었다.

 

각 원소의 존재여부를 행(row)로, 타겟 값(k)을 열(col)로 설정하여 DP 테이블을 만들어준 뒤, 초기 값을 설정해준 뒤 점화식을 도출하여 수월하게 풀이할 수 있었다.

 

DP 문제를 풀 때는 항상 작은 문제로 풀기 위해 '1. DP 테이블을 선언'하고, '2. 초기 값을 설정'한 뒤, '3. 점화식을 도출'해야 한다는 점을 잊지말자 :)