https://www.acmicpc.net/problem/2293
시간 0.5초, 메모리 4MB
input :
- n k(1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000)
- n개의 줄에는 각각의 동전의 가치가 주어진다.(1 <= 동전 <= 100,000)
output :
- 경우의 수를 출력.
조건 :
- 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
점화식을.... 생각하지 못해서 위의 분의 풀이를 보았다.
가지고 있는 동전의 가치들을 이용해서 idx - coin[i]에 해당 하는 dp의 값을 더해주는 방식을 이용해야 한다.
동전이 몇개나 들어올지 모르는 상태이기도 하고, 그래서 각 동전에 대한 점화식이 필요하다.
dp[i] += dp[i - item] 현재 돈 - 동전의 가치. 이를 통해서 몇가지 경우가 있는지를 알 수 있다.
인제 나도 박스로 해서 모든 경우를 그려보자...
import sys
n, k = map(int, sys.stdin.readline().split())
coin = []
for i in range(n):
coin.append(int(sys.stdin.readline()))
dp = [0] * (k + 1)
dp[0] = 1
for item in coin:
for i in range(1, k + 1):
if i - item >= 0:
dp[i] += dp[i - item]
print(dp[k])
