작은 지식주머니
백준 파이썬 9084 동전 본문
https://www.acmicpc.net/problem/9084
9084번: 동전
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는
www.acmicpc.net
DP로 풀수 있는 문제.
예전에 비슷한 문제를 푼 기억이 나서 금방 풀었다.
T = int(input())
for _ in range(T):
n = int(input())
s = list(map(int,input().split()))
goal = int(input())
dp = [0 for i in range(goal+1)]
dp[0] = 1
for i in s:
for j in range(1,goal+1):
if j - i >= 0:
dp[j] += dp[j-i]
print(dp[goal])
'백준 python 기록' 카테고리의 다른 글
| 백준 파이썬 11048 이동하기 (0) | 2022.04.05 |
|---|---|
| 백준 파이썬 6593 상범 빌딩 (0) | 2022.02.26 |
| 백준 파이썬 13023 ABCDE (0) | 2022.02.22 |
| 백준 파이썬 11000 강의실 배정 (0) | 2022.02.20 |
| 백준 파이썬 2470 두 용액 (0) | 2022.01.29 |
'백준 python 기록' Related Articles
more
Comments