[Python]백준 2293/동전 1 / dp

 

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

2293번: 동전 1

 

 

⚡️ 문제 설명

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 

⚡️ 해결 방법

	dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]	dp[7]	dp[8]
1	1	1 1개	1+1 1개	1+1+1 1개	1+1+1+1 1개	1+1+1+1+1 1개	1+1+1+1+1+1 1개	1+1+1+1+1+1+1 1개	1+1+1+1+1+1+1+1 1개
2			1+1 2 2개	1+1+1 2+1 2개	1+1+1+1 2+1+1 2+2 3개	1+1+1+1+1 2+1+1+1 2+2+1 3개	1+1+1+1+1+1 2+1+1+1+1 2+2+1+1 2+2+2 4개	1+1+1+1+1+1+1 2+1+1+1+1+1 2+2+1+1+1 2+2+2+1 4개	1+1+1+1+1+1+1+1 2+1+1+1+1+1+1 2+2+1+1+1+1 2+2+2+1+1 2+2+2+2 5개
5						1+1+1+1+1 2+1+1+1 2+2+1 5 4개	1+1+1+1+1+1 2+1+1+1+1 2+2+1+1 2+1+1+1+1 5+1 5개	1+1+1+1+1+1+1 2+1+1+1+1+1 2+2+1+1+1 2+2+2+1 5+2 5+1+1 6개	1+1+1+1+1+1+1+1 2+1+1+1+1+1+1 2+2+1+1+1+1 2+2+2+1+1 2+2+2+2 5+2+1 5+1+1+1 7개

 

coin=1일 때

coin 1
i =  1
dp [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
i =  2
dp [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
i =  3
dp [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
i =  4
dp [1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
i =  5
dp [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0]
i =  6
dp [1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0]
i =  7
dp [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
i =  8
dp [1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0]
i =  9
dp [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
i =  10
dp [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

coin=2 일 때

coin 2
i =  2
dp [1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1]
i =  3
dp [1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1]
i =  4
dp [1, 1, 2, 2, 3, 1, 1, 1, 1, 1, 1]
i =  5
dp [1, 1, 2, 2, 3, 3, 1, 1, 1, 1, 1]
i =  6
dp [1, 1, 2, 2, 3, 3, 4, 1, 1, 1, 1]
i =  7
dp [1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 1]
i =  8
dp [1, 1, 2, 2, 3, 3, 4, 4, 5, 1, 1]
i =  9
dp [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 1]
i =  10
dp [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]

coin=5 일 때

coin 5
i =  5
dp [1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 6]
i =  6
dp [1, 1, 2, 2, 3, 4, 5, 4, 5, 5, 6]
i =  7
dp [1, 1, 2, 2, 3, 4, 5, 6, 5, 5, 6]
i =  8
dp [1, 1, 2, 2, 3, 4, 5, 6, 7, 5, 6]
i =  9
dp [1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 6]
i =  10
dp [1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10]

 

>> 알고리즘

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

 

 

 

⚡️ 코드

import sys
input = sys.stdin.readline

n,k=map(int,input().split())

coins=[]
for _ in range(n):
    coins.append(int(input()))

dp=[0]*(k+1)
dp[0]=1

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

print(dp[k])