[python] 동전 1 (Baekjoon, 2293)

문제(Link) : https://www.acmicpc.net/problem/2293

백준에 있는 동적계획법(DP) 문제이다. 문제를 보고 점화식을 잘 세우는게 중요한데 이 문제는 점화식을 생각해 내기가 어려웠다.

동적 계획법(DP)라면 일단 '전체의 문제'를 '부분 문제'로 나눈 후, 부분 문제들을 해결하며 그 결과값들을 메모이제이션하는 것이 기본이다.

dp[i]를 동전들을 사용해서 i원을 만드는 경우의 수 라고 정의하고 i값을 증가시키며 dp[k]를 구할 것이다. 새로운 동전이 추가될 때마다 이 과정을 반복한다.

여기서 알아야 하는 두가지는
1. c원 동전을 기준으로 메모이제이션 할 때에는 c원보다 작은 가치의 배열은 고려할 필요가 없으므로 dp[c]부터 순회한다.
2. c원 동전 단 하나만 사용해서 j원을 만들 떄에는 c==j이기 때문에 dp[j-c] 즉, dp[0]은 1로 설정해놓아 1가지 경우의 수가 있음을 나타낸다.

from sys import stdin

n, k = map(int, stdin.readline().split())

coin = [0] * n
for i in range(n):
    coin[i] = int(stdin.readline())

dp = [1] + [0] * k
for i in range(n):
    for j in range(coin[i], k+1):
        dp[j] += dp[j-coin[i]]

print(dp[k])