잔돈 만드는 방법 (Coin change)

숫자(N)와 숫자의 집합(C = {C1, C2, C3, ...}이 주어졌을 때, C의 숫자들을 중복으로 사용하여 N을 만드는 방법의 수를 구해보자. 잔돈 문제로 바꾸어서 표현하면, 각각 값어치가 C1, C2, C3, ... 인 동전이 무한대로 주어질 때, 돈 N을 만들수 있는 동전들의 조합 방법은 얼마인지 찾아 보는 것이다.

대표적인 dynamic programming 문제로, top-down 방식과 bottom-up 방식으로 각각 풀어 본다.

우선, top-down 방식.

이해를 돕기 위해서 C1 >= C2 >= C3 >= ... 라고 가정을 하고 (반드시 정렬되어야 할 필요는 없음),

풀고자 하는 문제를

f(N, P) = {P번째로 작은 또는 그보다 작은 동전을 사용해서 돈 N을 만들는 방법의 수}

로 바꾸어 정의를 하면,

와 같이 재귀적으로 표현이 된다.

이 내용을 recursion을 사용하여 구현하면 되나, 곰곰히 들여다 보면 재귀함수를 호출할 때 사용되는 인자들이 자주 중복될 것이라는 발견할 수 있다. 중복적으로 호출되는 값들의 경우 매번 다시 계산하는 것보다는 계산 결과를 기억했다 재사용함으로서 연산 수행시간을 줄일 수 있다 (memoization).

func coinChangeTopDown(N, M int, data []int) int {

table := make([][]int, M)

for i := 0; i < M; i++ {

table[i] = make([]int, N+1)

for j := range table[i] {

table[i][j] = -1

}

}

return coinChange2Util(N, M, 0, data, table)

}

func coinChange2Util(N, M, P int, data []int, table [][]int) int {

if P == M {

if N == 0 {

return 1

}

return 0

}

if table[P][N] != -1 {

return table[P][N]

}

count := 0

for i := 0; N-i*data[P] >= 0; i++ {

count += coinChange2Util(N-i*data[P], M, P+1, data, table)

}

table[P][N] = count

return table[P][N]

}

이제, bottom-up 방식으로 접근을 해보자.

위 식을 오른쪽에서 왼쪽 (낮은 차원에서 높은 차원)으로 해석을 하면, N=0을 만들기 위한 경우의 수는 1이고 (모든 동전을 한번도 사용하지 않는 것), 여기서 시작해서 하나의 동전, 두 개의 동전, ..., 모든 동전을 사용해서 만들 수 있는 모든 돈의 경우의 수를 계산해 나가는 것이다.

예를 들어, 돈 10원을 동전 2, 3, 5, 6으로 만들어 보자.

초기 상태에는 0원만 1가지 방법으로 만들 수 있다.

돈		0	1	2	3	4	5	6	7	8	9	10
가지수	초기 상태	1	0	0	0	0	0	0	0	0	0	0
	2	0	0	0	0	0	0	0	0	0	0	0
	2,3	0	0	0	0	0	0	0	0	0	0	0
	2,3,5	0	0	0	0	0	0	0	0	0	0	0
	2,3,5,6	0	0	0	0	0	0	0	0	0	0	0

가장 작은 수인 2와 2의 배수로 만들 수 있는 방법을 계산한다. 이전 단계에서 조합이 가능한 0부터 시작해야 하고, 0+0, 0+2, 0+4, 0+6, 0+8, 0+10이 가능하여 0, 2, 4, 6, 8, 10을 만들 수 있는 가지수가 1이 된다.

돈		0	1	2	3	4	5	6	7	8	9	10
가지수	초기 상태	1	0	0	0	0	0	0	0	0	0	0
	2	1	0	1	0	1	0	1	0	1	0	1
	2,3	0	0	0	0	0	0	0	0	0	0	0
	2,3,5	0	0	0	0	0	0	0	0	0	0	0
	2,3,5,6	0	0	0	0	0	0	0	0	0	0	0

다음으로 3과 3의 배수로 만들 수 있는 가지수를 계산한다. 2만을 사용해서 만들 수 있는 수에 3의 배수를 더하여 만들어지는 돈의 가지수를 계산하면 된다. 계산 결과 돈 9는 2가지 경우로 만들 수 있는데, 동전2로 만든 돈6에 동전 3을 하나 더하는 방법과, 동전2로 만든 돈0에 동전 3을 3개 더하는 방법이 있기 때문이다.

돈		0	1	2	3	4	5	6	7	8	9	10
가지수	초기 상태	1	0	0	0	0	0	0	0	0	0	0
	2	1	0	1	0	1	0	1	0	1	0	1
	2,3	1	0	1	1	1	1	1	1	2	2	2
	2,3,5	0	0	0	0	0	0	0	0	0	0	0
	2,3,5,6	0	0	0	0	0	0	0	0	0	0	0

마찬가지 방법으로 동전 5까지 적용.

돈		0	1	2	3	4	5	6	7	8	9	10
가지수	초기 상태	1	0	0	0	0	0	0	0	0	0	0
	2	1	0	1	0	1	0	1	0	1	0	1
	2,3	1	0	1	1	1	1	2	1	2	2	2
	2,3,5	1	0	1	1	1	2	2	2	3	3	4
	2,3,5,6	0	0	0	0	0	0	0	0	0	0	0

동일한 방법으로 동전 6까지 적용.

돈		0	1	2	3	4	5	6	7	8	9	10
가지수	초기 상태	1	0	0	0	0	0	0	0	0	0	0
	2	1	0	1	0	1	0	1	0	1	0	1
	2,3	1	0	1	1	1	1	1	1	2	2	2
	2,3,5	1	0	1	1	1	2	1	2	3	3	4
	2,3,5,6	1	0	1	1	1	2	2	2	4	4	5

위 표에서 각 셀의 의미는 주어진 동전으로 돈을 만들 수 있는 가지수이고, 우리가 원하는 답은 맨오른쪽 아래인 동전 2,3,5,6으로 돈 10을 만드는 가지수인 5이다.

func coinChangeBottomUp(N, M int, data []int) int {

table := make([][]int, M+1)

for i := 0; i < M+1; i++ {

table[i] = make([]int, N+1)

}

table[0][0] = 1

for i := 1; i <= M; i++ {

for j := 0; j <= N/data[i-1]; j++ {

add := data[i-1] * j

for k := 0; k+add <= N; k++ {

table[i][k+add] += table[i-1][k]

}

}

}

return table[M][N]

}