[백준/Python]2293_동전 1

문제

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

2293번: 동전 1

풀이

다이나믹 프로그래밍을 이용해서 풉니다.

다이나믹 프로그래밍은 큰 문제를 작은 문제들로 나누어 푸는 것을 말합니다.

이 문제에서 동전 가치의 합이 k가 되는 조합의 수를 구하는 큰 문제를 동전별로 작은 문제로 나누어 풀 것입니다.

dp 배열의 index는 가치의 합을 나타내고 dp[index]는 가치 합이 index가 되는 동전 조합의 수를 나타냅니다.

dp를 0으로 초기화하고 dp[0]은 동전 한 개의 경우이므로 1을 넣습니다.

그 후, 동전의 종류별로 동전 크기를 간격으로 dp[j] += dp[j - coin]를 수행하면 최종 dp[k]의 값을 구할 수 있습니다.

코드

import sys

n, k = map(int, sys.stdin.readline().rstrip().split())
coins = []
dp = [0] * (k + 1)
dp[0] = 1
for _ in range(n):
    coins.append(int(sys.stdin.readline().rstrip()))
for coin in coins:
    for j in range(coin, k + 1):
        dp[j] += dp[j - coin]
print(dp[k])