728x90
SMALL
DP 문제
https://www.acmicpc.net/problem/9084
9084번: 동전
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는
www.acmicpc.net
💡 풀이 코드
import sys
t = int(sys.stdin.readline())
for _ in range(t):
n = int(sys.stdin.readline())
c = list(map(int, sys.stdin.readline().split()))
price = int(sys.stdin.readline())
dp = [[0] * (price + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
dp[i][0] = 1
def coin(n, c, price):
for i in range(1, n + 1):
for j in range(1, price + 1):
if j - c[i - 1] < 0 : coinComb = 0
else: coinComb = dp[i][j - c[i - 1]]
dp[i][j] = dp[i - 1][j] + coinComb
coin(n, c, price)
print(dp[n][price])
728x90
LIST
'Algorithm > DP' 카테고리의 다른 글
[백준] 2294번 : 동전 2 (파이썬) (0) | 2024.02.18 |
---|---|
[백준] 11054번 : 가장 긴 바이토닉 부분 수열 (파이썬) (2) | 2024.01.22 |
[백준] 2565번 : 전깃줄 (파이썬) (0) | 2024.01.20 |
[백준] 9465번 : 스티커 (파이썬) (1) | 2024.01.06 |
[백준] 11053번 : 가장 긴 증가하는 부분 수열 (파이썬) (1) | 2024.01.05 |