[Python] BOJ no.9084 동전

문제 링크

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

9084번: 동전

---

문제 설명

9084, 동전 문제는 주어지는 동전의 단위로 어떤 금액을 만들 수 있는 개수를 구하는 프로그램을 작성하면 된다. 다이나믹 프로그래밍(DP) 유형의 알고리즘으로 이전의 값들을 사용해 문제에서 요구하는 금액을 만들 수 있는 조합의 개수를 구하면 된다.

---

내 풀이

DP를 사용하야 풀 수 있다는 생각은 하고 있었고, 비슷한 Logic을 떠올리는데는 성공했다. 하지만 구체적인 코드가 생각나지 않았다.. ㅜㅜ

---

풀이 #1

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

  d = [0] * (m+1)
  d[0] = 1
  for coin in coins:
    for i in range(coin, m+1):
      d[i] += d[i-coin]

  print(d[m])

1. 먼저 테스트 케이스 개수를 받아온다. (t)
2. 테스트 케이스 별로 동전 단위의 개수(n), 화폐가 되는 동전 리스트(coins), 목표 금액(m)을 받아온다.
3. DP공간(d)을 만들어주고 (초기에는 모든 금액을 만드는 개수를 0으로 초기화) 0원을 만들기 위한 개수는 1개이므로 'd[0] = 1'을 넣어준다.
4. for 문을 도는데 '에라토스테네스의 체' 알고리즘처럼 가장 작은 coin부터 만들 수 있는 값들을 모두 채워준다.
   1. 예시로 coin은 5, 7이 있고 목표금액은 22라고 해보자.
   2. 먼저 5부터 for문을 시작해보면, 5는 0 + 5로 1가지, 10은 5(직전의 0 + 5 ) + 5로 1가지, 15는 1가지... 이런식으로 0에 의한 5의 배수들이 1가지 방법으로 추가가 된다.
   3.  이후 7에 대해 진행해보자. 먼저 기존 1가지를 가지고 있는 0에 7을 더한 7에 1가지, 5에 1가지를 가지고 있으니 12 (5 + 7)에 1가지, 계속해서 14 (7 + 7), 17 (10 + 7), 19 (12 + 7), 22 (17 + 5) 이런식으로 가지고 있는 방법수를 계승해서 가지고 올라가고 만약 다른 방법에 추가가 되더라도 중복적으로 해당 값은 추가가 되므로 만족할 수 있다. (5와 7의 배수 35 -> 5로만 35 만드는 1가지 + 7로만 35 만드는 1가지 = 2가지)

 

이 문제를 푸는 방법에 대해서 고민했을 때 이전값에 coin만큼 증가한 dp 공간에 더해줘야겠다는 생각은 했지만 만약 1이 아닌 2,3,4 와 같은 큰 값을 가지고 있을 때는 그 값을 만드는 방법의 개수를 단순히 더하는 것으로 만족시킬 수 있을지 고민하게 되었다.

예를 들어, coin은 1,2이라면 3을 만드는 방법은 2가지(1+1+1, 1+2)이다. 그럼 위의 알고리즘으로 3을 채워보자.
d[3] = 0, d[3] += d[2](coin=1), d[3] += d[1](coin=2)
먼저, d[3]을 1로 채우는 경우에는 1+1(2) +1인 1가지가 추가되고 2로 채우는 경우는 1 + 2인 1가지가 추가되어 2가지가 된다.
이때, coin이 오름차순으로 계산되는 것을 고려하지 않고 모두 계산한다면 d[2] + 1의 과정에서 d[2]는 2 (1+1, 2)이기 때문에 d[3]을 3으로 잘못 계산할 수 있다. (즉, 2 중 for문의 순서도 고려해야한다. -> 둘이 바뀐다면 위의 문제가 발생할 수 있음)