[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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

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))