[백준 / Python] 동전 1_2293

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

n, k = map(int, input().split())
data = []
for _ in range(n):
    data.append(int(input()))

counts = [0 for _ in range(10001)]
counts[0] = 1

for coin in data:
    for price in range(10001):
        if price >= coin:
            counts[price] += counts[price-coin]

print(counts[k])

 

이 문제는 전형적인 DP문제이다.

DP에서는 분할정복과 같은 방법으로 문제를 작은 부분문제로 나눠서 풀고, 캐시하여 재사용될 때 활용해 해결하는 것이다.

왜 이전의 counts값을 더하는걸까?

-> 가장 작은 단위의 부분 문제로 본다면, 

counts[price-coin]은 가격에서 해당 coin을 뺀 값이다.

counts[price-coin]은 해당 가격까지의 모든 경우의 수를 담고 있고, 그 가격에서 현재의 coin만 더하면

coin에 해당하는 counts[price]값을 구할 수 있다.