알고리즘/[python] 백준 BOJ
[python] 백준 9084 동전
Alan_Kim
2023. 3. 22. 19:54
728x90
반응형
https://www.acmicpc.net/problem/9084
9084번: 동전
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는
www.acmicpc.net
문제 해결
- dp[i]는 i원을 만드는데 가지수를 나타내는 것이다.
- 1원부터 $10^{4}$까지 차례로 dp를 통해 나타낸다.
- 동전이 있는것은 1개로 되므로 dp[coin]은 1이상이다.
CODE
for _ in range(int(input())):
n = int(input())
coins = list(map(int, input().split()))
total = int(input())
dp = [0]*(total+1)
dp[0] = 1
for coin in coins:
for i in range(total+1):
if i >= coin:
dp[i] += dp[i-coin]
print(dp[total])728x90
반응형