[백준] 2293 - 동전1 [Python(파이썬)]

문제

www.acmicpc.net/problem/2293

2293번: 동전 1

풀이

k	0	1	2	3	4	5	6	7	8	9	10
coin	0	0	0	0	0	0	0	0	0	0	0
1	1	0+1=1	0+1=1	0+1=1	0+1=1	0+1=1	0+1=1	0+1=1	0+1=1	0+1=1	0+1=1
2	1	1	1+1=2	1+1=2	1+2=3	1+2=3	1+3=4	1+3=4	1+4=5	1+4=5	1+5 = 6
5	1	1	1	2	3	3+1=4	4+1=5	4+2=6	5+2=7	5+3=8	6+4=10

 

생각하기 쉽도록 테이블을 그려본다. 세로 축은 동전, 가로 축은 만들 수 있는 값이 된다.

dp테이블엔 만들 수 있는 값의 경우의 수가 담긴다.

 

n원를 만들 수 있는 경우의 수는 이전 행의 n원을 만들 수 있는 경우의 수와 n원에서 현재 동전의 가치 k원를 뺀 가치의 경우의 수의 합으로 이루어진다.

 

이것을 점화식으로 표현하면 다음과 같다.

dp[n] = dp[n] + dp[n-k] (if n-k >= 0)

 

코드

import sys

n, k = map(int, sys.stdin.readline().split())
coins = []
dp = [0 for _ in range(k+1)] 
dp[0] = 1

for _ in range(n):
    coins.append(int(sys.stdin.readline().strip()))

coins = list(set(coins)) # 중복 제거

for coin in coins:
    for i in range(1, k+1):
        if i - coin >= 0:
            dp[i] += dp[i-coin]

print(dp[k])