[백준] 9084 동전

📖 문제

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

💻 내 코드

import sys
t=int(sys.stdin.readline())

for _ in range(t):
    n=int(sys.stdin.readline())
    coin=list(map(int, sys.stdin.readline().split()))
    money=int(sys.stdin.readline())

    dp=[0]*(money+1)
    dp[0]=1
    for i in coin:
        for j in range(i, money+1):
            dp[j]+=dp[j-i]

    print(dp[money])

💡 풀이

• dp 리스트를 주어진 금액의 크기만큼 만든다
• dp[0]=1로 저장
• 금액 i를 만들 수 있는 방법의 수를 $a_i$라 하고 동전의 단위를 $k$라고 했을 때
• $a_{i-k}$를 만드는 방법이 존재할 경우: $a_i+=a_{i-k}$
• $a_{i-k}$를 만드는 방법이 존재하지 않을 경우: $a_i=a_i$가 된다
• 이를 코드로 나타내면 다음과 같다

for i in coin:
        for j in range(i, money+1):
            dp[j]+=dp[j-i]