[Dynamic Programming] 동전 1

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

Description

n가지 종류의, 가치가 서로 다른 동전이 주어진다. 이 동전들로 총합 k원을 만들고자 할 때 모든 경우의 수를 구하는 문제이다.

Idea

dp : (k * n) 2차원 배열 values: 동전의 가치의 배열 dp[i][j]  : 총합 i원을 만드는데, 가장 큰 가치를 갖는 동전이 values[j]원인 경우의 수 위와 같이 정의하면,

1. i < values[j] 일때 : dp[i][j] = 0
2. i =values[j] 일때 : dp[i][j] = 1
3. i > values[j] 일때 : dp[i][j] = dp[i - j][0] + dp[i - j][1] + ... + dp[i - j][j]

이다.

Code

def solve(k, dp, values):
    #rowwise iteration through dp (it is k * n 2d list!)
    for i in range(k+1):
        for j in range(len(values)):
            #case 1 : i < values[j] -> dp[i][j] = 0
            if i < values[j]:
                dp[i][j] = 0
            #case 2 : i == values[j] -> dp[i][j] = 1
            elif i == values[j]:
                dp[i][j] = 1
            #case 3 : i > values[j] -> dp[i][j] = sum(dp[i-values[j]][0, 1, ..., j])
            else:
                dp[i][j] = sum([dp[i-values[j]][x] for x in range(j+1)])

    return sum([dp[k][x] for x in range(len(values))])


if __name__ == '__main__':
    #parse input
    n, k = [int(i) for i in input().split()]
    values = [int(input()) for _ in range(n)]

    #make dp list
    dp = [[-1] * n for _ in range(k+1)]

    #answer
    print(solve(k, dp, values))