[백준][Python] 9084번 동전 - 코팩

문제

https://www.acmicpc.net/problem/9084

9084번: 동전

 

풀이

문제를 풀기 위해서 다음과 같은 점화식이 필요하다.

주어진 화폐 단위 별로 해당하는 금액을 완성할 수 있는 동전을 구성하는 개수를 찾아준다.

 

1. dp[0]을 1로 초기화합니다. 이는 금액 0을 만드는 방법이 하나밖에 없음을 의미합니다(아무 동전도 사용하지 않는 경우).

2. 모든 동전 단위 coin[i]에 대해 반복합니다.

3. 각 coin[i]에 대해 금액 coin[i]부터 목표 금액 k까지 금액 j에 대해 위의 점화식을 적용하여 dp[j]를 업데이트합니다.

 

코드

# 9084번 동전
import sys
input = sys.stdin.readline

t = int(input())
# 다이내믹 프로그래밍 사용
for _ in range(t):
    # 동전 종류의 개수
    _ = int(input())
    # 동전의 단위
    coin = list(map(int, input().split()))
    # 동전으로 만들어야할 금액
    k = int(input())
    # 다이내믹 프로그래밍 사용을 위한 메모제이션 사용
    dp = [0] * (k+1)
    dp[0] = 1

    for i in coin:
        for j in range(1, k+1):
            # 동전의 단위보다 큰 금액일 경우
            if j >= i:
                dp[j] += dp[j-i]

    print(dp[k])

 

출력결과