💡문제접근
- 테스트케이스를 예제로 점화식을 세워보았다.
- 1원을 이용해서 1 ~ 10원을 만드는 방법의 수는 모두 1가지가 나온다.
- 1, 2원을 이용해서 1 ~ 10원을 만드는 방법의 수를 단계적으로 살펴보자.
1) 1원을 만들 수 있는 경우의 수 : 0
2) 2원을 만들 수 있는 경우의 수 : 1
3) 3원을 만들 수 있는 경우의 수 : 1.....- 위와 같은 방식을 이용해서 점화식을 구성할 수 있다.
💡코드(메모리 : 31256KB, 시간 : 232ms)
import sys
input = sys.stdin.readline
n, k = map(int, input().strip().split())
coins = []
for _ in range(n):
coins.append(int(input()))
dp = [0] * (k+1)
dp[0] = 1 # 0원을 만들 수 있는 방법의 수 : 1가지
for coin in coins:
for i in range(coin, k+1):
cnt = dp[i - coin]
dp[i] += cnt
print(dp[k])💡소요시간 : 18m
🐢