동전 교환(CC: Coin Change)

동전 교환(CC: Coin Change)은 다이나믹 알고리즘 중 하나입니다. CC는 동전의 종류들로 특정 금액을 만드는 경우의 수를 구하는 알고리즘입니다.

예를 들어서 1원, 2원, 5원, 10원 4가지 종류의 동전으로 10원을 만드는 경우의 수를 구해보겠습니다.
동전의 가치는 cost 배열에 넣었다고 생각하겠습니다.
즉, cost[] = {0, 1, 2, 5, 10} 입니다.

 

모든 경우의 수를 구하기 위해서는 2차원 배열이 필요합니다.
d[i][j] = i가지 종류의 동전을 사용해서 j금액을 만드는 모든 경우의 수
입니다.
따라서 우리가 구하고자 하는 경우의 수는 d[4][10]이 됩니다.
이제 배열을 채워봅시다.

 

[0행]

0행은 0원으로 j금액을 만드는 경우의 수라고 생각하변 됩니다.
0금액을 만드는 방법은 아무것도 안해도 되므로 1가지이고 그 외에는 0으로 채워줍니다. 

 

[1행]

1행은 1원으로 j금액을 만드는 경우의 수입니다.
1원으로 j금액을 만드는 방법은 동전을 모든 금액이든 1가지 방법밖에 없으므로 1입니다.

 

 

 

2행

지금부터가 중요합니다.
2행은 2가지 종류로 j금액을 만드는 경우의 수입니다.

2원은 0원과 금액1을 만들 수 없으므로
d[2][0] = d[1][0], d[2][1] = d[1][1] 입니다.

d[2][2]는 0원에 2원 1개를 추가하여 금액2를 만들 수 있고(d[2][0]) 아까 구한 1가지 종류로 금액2를 만드는 경우의 수(d[1][2])를 더한 수입니다. 
즉, d[2][2] = d[2][0] + d[1][2] 입니다.
주의해야 할 것은 0원에 2원 1개를 추가한다고 해서 경우의 수도 +1이 되는 것이 아니라, 0원에 2원 1개를 추가해서 금액 2를 만들 수 있으므로 d[2][0]의 경우의 수를 그대로 가져와야 합니다.

마찬가지로 d[2][3]은 1원에 2원 1개를 추가하여 금액 3을 만들 수 있고(d[2][1]) 1가지 종류로 금액 3을 만드는 것(d[1][3])도 d[2][3]에 포함되므로 두개를 더한 수가 됩니다.
즉, d[2][3] = d[2][1] + d[1][3] 입니다.

규칙을 찾아보면
d[2][j] = d[1][j] (0 <= j < cost[2])
            = d[2][j-2] + d[1][j] (cost[2] <= j)
입니다.

 

3행

3행도 위에서 설명한 것과 같습니다.
d[3][j] = d[2][j] (0 <= j < cost[3])
            = d[3][j-cost[3]] + d[2][j] (cost[3] <= j) 
로 3행을 채울 수 있습니다. 빨간 글씨는 2행을 채우는 수식과 다른 점인데, 행이 +1이 됨에 따라 빨간색 수 또한 +1이 됩니다.

따라서
d[i][j] = d[i-1][j] (0 <= j < cost[i])
          = d[i][j-cost[i]] + d[i-1][j] (cost[i] <= j)
라는 공식을 구할 수 있습니다.

 

 

[4행]

4행을 위의 공식에 따라서 채워보면 0 ~ 10(cost[i]-1) 까지는 d[3][j]와 같고
d[4][10]은 d[4][0] + d[3][10]으로 11이 됩니다.

정답은 d[4][10] = 11이 됩니다.

 

---

동전의 개수(n)와 만들고자 하는 금액(money)를 입력받고 n개의 동전 가치를 입력받습니다.
그리고 n가지의 동전으로 money를 만드는 경우의 수를 출력합니다.
 
소스 코드 : https://gist.github.com/fpdjsns/e280f244b56eaab4f921dbe07a209acb

실행결과