[백준/파이썬] 2293 : 동전 1

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

2293번: 동전 1

문제 요약 : n개의 동전이 주어졌을 때, 그 동전들로 k원을 만들 수 있는 경우의 수를 출력하라

 

풀이 )

DP문제는 최적화 문제를 해결하는 알고리즘이다.

 

그렇기 때문에 전체 문제를 부분으로 나누어 생각하여야 한다.

부분문제를 해결하면서 얻은 결과 값이 메모이제이션을 하는지, 점화식을 세울 수 있는지를 신경쓰며 푼다.

 

 

테스트 케이스였던 1,2,5를 이용하여 10을 만드는 경우의 수를 구하여 보겠다.

먼저 1을 가지고는 모든 숫자를 만들 수 있으며 경우의 수는 모두 1이다. 

 

 

다음으로 1과 2를 가지고 만들 수 있는 경우의 수를 생각해보겠다.

일단 2보다 작은 숫자를 만들 수 없기 때문에 dp[2]부터 채워나간다.

 

 

이때 2와 3은 1로 만든 경우의 수에 하나만 더 해주면 되지만,

4같은 경우는 1+1+1+1, 1+1+2, 2+2 같이 세가지 경우가 존재한다.

원래 있던 dp[4](1+1+1+1)에 dp[2]에 2코인을 하나 더 붙인 경우(1+1+2, 2+2)를 더 해주는 것임을 알 수 있다.

 

 

그래서 점화식을 세워보면 dp[i] += dp[i-coin] 이 되는 것이다.

n,k = map(int,input().split())
a = list(int(input()) for _ in range(n))
dp = [0] * (k+1)
dp[0] = 1

for i in a :
    for j in range(i,k+1):
        dp[j] += dp[j-i]
        
print(dp[k])