🪙 백준 9084번:동전(DP)

---

🧐 문제 해석

• 각 테스트의 개수 마다 지불할 수 있는 방법의 수를 출력한다.
• 금액의 종류가 주어지며 각 동전은 무한하다고 가정한다.

🎯 목표:

N가지의 동전 종류가 주어졌을 때 M이라는 금액을 만들 수 있는 모든 경우의 수의 개수를 출력한다.

---

🔍 핵심 아이디어

이 문제는 knapsack 알고리즘을 적용시킬 수 있는 DP 문제이다.

✅ DP 테이블 용도

• dp[i][j] : i개 종류의 동전을 사용했을때 j라는 금액을 만들 수 있는 최대 방법의 수

---

📌 핵심 포인트

🔶 첫번째 동전만 사용하는 경우

반복문으로 dp테이블을 조사하기 전 초기값 설정을 위해 첫번째 동전에 대한 dp테이블 값을 조사한다.

for j in range(0, total + 1):
    if j % coins[0] == 0:
        dp[0][j] = 1

첫번재 동전으로 j라는 금액을 만들 수 있다면 1이다.

🔶 i번째 동전을 사용하는 경우

for i in range(1, n):
    for j in range(total + 1):
        dp[i][j] = dp[i - 1][j]
        if j >= coins[i]:
            dp[i][j] += dp[i][j - coins[i]]

• dp[i][j]는 기본적으로 현재 내 손에 있는 i번째 동전까지만 사용했을때의 값을 기본 값으로 가져와야 한다.
  • 즉, 내 손에 있는 동전을 사용하지 않는 경우를 먼저 기록한다.
• 만약 내 손에 있는 동전을 사용해서도 해당 금액을 만들 수 있다면 그 금액을 사용하는 경우를 더해준다
  • j-coins[i] : i번째 동전으로 j라는 금액을 채울 것이기 때문에 딱 i까지만 채워진 dp 최적해에 현재 최적해를 더해준다.

즉,

• dp[i][j] = dp[i - 1][j]: i번째 동전을 사용하지 않는 경우 (이전 동전으로만 구성)
• dp[i][j] += dp[i][j - coin[i]]: i번째 동전을 한 번 이상 사용하는 경우

---

💯 정답

t = int(input())

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

    dp = [[0] * (total + 1) for _ in range(n)]

    
for j in range(0, total + 1):
    if j % coins[0] == 0:
        dp[0][j] = 1
print(dp)

for i in range(1, n):
    for j in range(total + 1):
        dp[i][j] = dp[i - 1][j]
        if j >= coins[i]:
            dp[i][j] += dp[i][j - coins[i]]

print(dp[n - 1][total])

---

💭 생각

✅ 결론 한 줄

정말 knapsack 그 자체의 문제다

---

😮‍💨 DP...

아직 문제를 많이 풀어보지는 못했지만 정말 어렵다.
점화식 세우는 것도, 뭘 관계인자로 봐야될지도 정말 모르겠다.
knapsack 알고리즘 정리하고 자신만땅이었는데 고작 물건이 동전으로 바뀌고 가방이 금액으로 바뀐 문제에서부터 헤매다니 흑흑이다 정말 ~