문제 바로가기
문제:
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다. 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오. 편의를 위해 방법의 수는 231 - 1 보다 작다고 가정해도 된다.
입력:
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 첫 번째 줄에는 동전의 가지 수 N(1 ≤ N ≤ 20)이 주어지고 두 번째 줄에는 N 가지 동전의 각 금액이 오름차순으로 정렬되어 주어진다. 각 금액은 정수로서 1원부터 10000원까지 있을 수 있으며 공백으로 구분된다. 세 번째 줄에는 주어진 N가지 동전으로 만들어야 할 금액 M(1 ≤ M ≤ 10000)이 주어진다.
출력:
각 테스트 케이스에 대해 입력으로 주어지는 N가지 동전으로 금액 M을 만드는 모든 방법의 수를 한 줄에 하나씩 출력한다.
풀이:
import sys
T = int(input())
def coin_dp(n, coins, m):
dp = [0] * (m+1)
for i in range(n):
# 어떤 코인을 주던 coin 에 해당하는 값은 1개
dp[coins[i]] += 1
for j in range(coins[i],m+1):
# 새로운 dp[j] 를 만드는 경우의 수는 dp[j-coin] + 기존 dp[j]
dp[j] += dp[j -coins[i]]
return dp[m]
for _ in range(T):
# 동전의 가짓수
n = int(input())
# 동전 오름차순
coins = list(map(int,input().split()))
# 맞춰야 하는 돈
m = int(input())
print(coin_dp(n,coins,m))
만약 100원 200원 300원 이고, 목표금액이 천원인 경우
dp[coin] 은 1이 추가 된다.
100원 만드는 방법은 1 >> 100
200원 만드는 방법은 2개 >> 100 100 / 200
300원 만드는 방법은 2개 >> 100 100 100/ 100,100
그리고, 100원 단위로 1씩 추가된다. dp[200] = 1, dp[300] = 1 이런식으로
다음코인 200원이 돌때 dp[200] 에 1개 추가돼서 2개가 된다.
이것을 점화식으로 쓰면
새로운 dp[j] = 기존의 j 만드는 경우의수 dp[j] + dp[j-coins[i]] (j-coin 만드는 경우의수) 를 더해주면 된다.
댓글