[Python] 백준 9084번 - 동전

📖 문제

9084번: 동전

 

🔎 풀이

배낭 문제 풀이법으로 풀 수 있는 DP 문제입니다. 시간 복잡도는 O(M + N)으로 2차원 테이블을 만들어 해결할 수 있습니다. 각 동전의 종류 N가지 만큼 M + 1개의 원소를 가지고 있는 배열을 만들고, 동전 종류 별로 테이블을 채워나가면 됩니다.

 

아래 코드에서는 1차원 배열만으로도 해결할 수 있습니다. 핵심은 현재 금액(M)에서 동전의 금액을 빼 준 값을 인덱스로 하여, 해당 인덱스의 원소를 더해주는 것입니다. 예를 들어 현재 금액이 10원이고, 동전 종류가 5원이라면 table[10-5]의 값을 현재 table[10]의 값에 더해줍니다.

 

💻 코드

for _ in range(int(input())):
    n = int(input())
    coins = list(map(int, input().split()))
    m = int(input())

    table = [0] * (m + 1)
    table[0] = 1

    for i in range(n):
        k = coins[i]
        for j in range(k, m+1):
            table[j] += table[j-k]

    print(table[-1])