[백준] 9084번 동전

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

이코테 다이나믹 프로그래밍의 효율적인 화페 구성 문제와 같은 줄 알고 동일하게 풀었으나 틀렸다,,

다른 방법이 떠오르지 않아 결국 구글링을 하게 되었다.

• 틀린 코드

t = int(input())

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

    # dp 테이블 초기화
    d = [10001] * (m + 1)
    d[0] = 1

    for i in range(n):
        for j in range(money[i], m + 1):
            d[j] = min(d[j], d[j - money[i]] + 1)
    print(d[m])

만들려고 하는 돈이 가지고 있는 화폐단위보다 크거나 같을 경우, 이전 경우의 수에 현재 동전으로 만들 수 있는 경우의 수를 더하면 된다.

• 구글링하여 수정한 코드

# 9084 : 동전

import sys
input = sys.stdin.readline

t = int(input())

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

    # dp 테이블 초기화
    d = [0] * (m + 1)
    d[0] = 1

    for coin in coins:
        for i in range(m + 1):
            if i >= coin:
                d[i] += d[i - coin]
    
    print(d[m])

예시로 한번 해봤으면 해결할 수도 있었을 것 같은데 아쉬운 문제이다. dp 문제는 규칙성을 잘 파악하고 점화식을 잘 세워야 하는 것 같다.

Uploaded by Notion2Tistory v1.1.0