문제
9084호：동전
한국 화폐 단위로는 1원, 5원, 10원, 50원, 100원, 500원이 있는데 특히 동전이 있습니다.
이러한 동전은 정수 금액을 형성할 수 있으며 이를 수행하는 방법에는 여러 가지가 있습니다.
예를 들어 30원을 벌려면
www.acmicpc.net
설명
동전이 주어지면 문제는 M을 만드는 방법의 수를 찾는 것입니다.
예시에 나온 샘플 하나로 어떻게 1000원, 1원, 2원을 만들 수 있을까요?
dp = (0 for _ in range(M+1))
dp(0) = 1먼저 동적 프로그래밍(DP)을 준비하기 위해 dp 배열을 만듭니다.
그리고 0번째 지수는 어떤 코인이든 0으로 이길 수 있는 경우가 모두 있기 때문에 1로 변경됩니다.
05원 있으면 0원, 010원 있으면 0원, 0100원 있으면 0원 받기 때문입니다.
for i in coin :
for j in range(1, M+1) :
if j >= i :
dp(j) += dp(j-i)
print(dp(M))이제 각 코인에 대해 양을 늘려 DP를 계산합니다.
dp(j)는 원을 형성하는 방법의 수를 의미합니다.
i-won 동전을 사용하여 j-won을 만들 수 있는 경우 dp(j)에 dp(ji)의 가능한 경우의 수를 더합니다.
모든 동전에 대해 반복하고 dp(M)을 출력하여 M개의 원을 만드는 방법의 수를 인쇄합니다.
여담으로 지문과 정답이 100% 일치하는 문제가 있다.
Solved.ac 검토를 원하시면 아래 질문을 하셔야 합니다.
3067호: 동전
한국 화폐 단위로는 1원, 5원, 10원, 50원, 100원, 500원이 있는데 특히 동전이 있습니다.
이 동전으로 모든 정수 금액을 만들 수 있으며 이를 수행하는 방법에는 여러 가지가 있습니다.
예를 들어 30원을 벌려면
www.acmicpc.net
from sys import stdin
input = lambda : stdin.readline().strip()
T = int(input())
for _ in range(T) :
N = int(input())
coin = list(map(int, input().split()))
M = int(input())
dp = (0 for _ in range(M+1))
dp(0) = 1
for i in coin :
for j in range(1, M+1) :
if j >= i :
dp(j) += dp(j-i)
print(dp(M))