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

문제) 백준 - 동적 계획법 (Dynamic programming) - 동전 1

-> www.acmicpc.net/problem/2293

2293번: 동전 1

 

주어진 동전들을 이용해서 k원을 만드는 방법의 수를 구하는 것이다. 아래 <표 1>을 보자. dp[k]를 만들 수 있는 경우의 수라 하자.

i(화폐가치)가 1일 때 dp[5] = dp[4]이다. 엄밀히 말하면, 현재 dp[5] 값이 0이기 때문에 dp[5] = dp[5] + dp[4]라 볼 수 있다.

i(화폐가치)가 2일 때 dp[5] = dp[5] + dp[3]이다.

i(화폐가치)가 5일 때 dp[5] = dp[5] + dp[0]이다.

 

<표1>

이로 미루어 볼 때 우리는 다음과 같이 정리할 수 있다.

1. 각 동전의 종류에 따라 순회한다.

2. index를 1원부터 k원까지 반복문을 돌리면서 동전의 값보다 큰 index에 대하여 dp[index] += dp[index - coin]을 진행한다.

 

 

 

 

소스 코드)

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
coin = []
for i in range(n):
    coin.append(int(input()))

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