[알고리즘] 동전 교환 알고리즘 개념, 구현

동전 교환 알고리즘

개념

편의점 아르바이트생인 A는 야간에 편의점 알바를 하고 있어요. 막상 편의점에 도착해서 보니까 동전이 없습니다. 그래서 사장님께 전화를 걸었으나, 이미 술취해서 뻗어버린 상태입니다. 할 수 없이 일단 가지고 있는 동전으로 거스름돈을 주며 내일 아침 사장님이 올때까지 뻐겨야하는 상황이 발생했습니다.

그러기 위해서는 거스름돈에 사용되는 동전의 갯수를 최소로 사용하여 주어야하는데 어떻게 최소 동전 갯수를 구할 수 있을까요?

현실에서는 10원, 50원, 100원, 500원의 동전이 있지만 여기서는 1, 4, 5, 6원의 동전이 있다고 가정하도록 하겠습니다. 만약 23원의 거스름돈을 위의 동전을 최소로 사용해 거슬러준다면 어떻게 거슬러주면 될까요? 여러가지가 있지만, 우선 가장 큰 값인 6을 먼저주고 남은것은 그 다음 큰 동전으로 사용한다면 6원 3개, 5원 1개로 23원을 만들 수 있습니다. 동전을 최소로 사용해서 준 것 맞습니까?

네, 가장 최소의 동전을 사용해서 준 것이 맞습니다.

항상 최대값의 동전을 우선적으로 사용해서 얻은 결과가 바로 답일까요? 일리있어 보이지만 항상 그렇지 않습니다.

14원을 예로 한번 들어보도록 합시다.

위의 방식대로 한다면 6원 2개, 1원 2개, 4개의 동전을 사용해서 14원을 만들 수 있습니다.

하지만 5원부터 주게되면 5원 2개, 4원 1개로 3개의 동전을 사용해서 14원을 만들 수 있습니다.

이제부터 어떻게 구할지 생각해보도록 하겠습니다.

우선 동전 하나를 가지고 얼마를 만들 수 있을지 생각합시다. 우선 1원입니다. 1원은 모든 수를 전부 만들 수 있습니다. 그렇다면 아래의 표와 같겠네요.

1원 사용시

거스름 돈	동전 갯수(1원 갯수, 4원 갯수, 5원 갯수, 6원 갯수)
1	1(1,0,0,0)
2	2(2,0,0,0)
3	3(3,0,0,0)
4	4(4,0,0,0)
5	5(5,0,0,0)
6	6(6,0,0,0)
7	7(7,0,0,0)
8	8(8,0,0,0)
9	9(9,0,0,0)
10	10(10,0,0,0)
11	11(11,0,0,0)
12	12(12,0,0,0)
13	13(13,0,0,0)
14	14(14,0,0,0)

4원을 사용한다면 4원은 당연히 한개로 만들 수 있고, 5원은 그 전의 1원과 합쳐서 만들 수 있습니다. 그렇다면 5원은 2개로 만들 수 있겠군요. 8원은 그전의 4원 2개로 만들 수 있습니다.

9원은 어떻겠습니까? 그전에 5원을 2개의 동전으로 구했었습니다. 1원과 4원을 합쳐서 말입니다. 여기에 4원을 더 얹으면 9원 아닌가요? 그래서 1원 1개, 4원 2개로 9원을 만들 수 있습니다. 그렇다면 표가 다음과 같이 바뀝니다.

4원 사용시

거스름 돈	동전 갯수(1원 갯수, 4원 갯수, 5원 갯수, 6원 갯수)
1	1(1,0,0,0)
2	2(2,0,0,0)
3	3(3,0,0,0)
4	1(0,1,0,0)
5	2(1,1,0,0)
6	3(2,1,0,0)
7	4(3,1,0,0)
8	2(0,2,0,0)
9	3(1,2,0,0)
10	4(2,2,0,0)
11	5(3,2,0,0)
12	3(0,3,0,0)
13	4(1,3,0,0)
14	5(2,3,0,0)

이제 5원을 사용하도록 합시다. 5원을 사용하게 되면 5원은 동전 한개로 만들 수 있고, 6원은 1원의 동전화 합쳐서 만들 수 있겠습니다. 10원은 5원 두개로 만들 수 있고 11원이 그 전의 6원을 만들었던 것에서 5원을 추가하여 만들 수 있답니다. 

5원 사용시

거스름 돈	동전 갯수(1원 갯수, 4원 갯수, 5원 갯수, 6원 갯수)
1	1(1,0,0,0)
2	2(1,0,0,0)
3	3(1,0,0,0)
4	1(0,1,0,0)
5	1(0,0,1,0)
6	2(1,0,1,0)
7	3(2,0,1,0)
8	2(0,2,0,0)
9	2(0,1,1,0)
10	2(0,0,2,0)
11	3(1,0,2,0)
12	3(0,3,0,0)
13	3(0,2,1,0)
14	3(0,1,2,0)

이제 감이 오시나요?

결국 현재의 동전만큼을 뺀 거스름돈에서 현재 동전하나를 추가하여 만드니까 그 전의 거스름돈에 1을 더하면 됩니다. 

하지만 이미 구해진 거스름돈이 더 적은값을 가지고 있다면 현재의 값을 유지하면 되는 것입니다. 그래서 이런 식이 나오게 됩니다.

dp[j] = MIN(dp[j], dp[j - coin[i]] + 1); 

dp[j]는 현재 구할 거스름돈의 값입니다. 그래서 현재 거스름돈에서 현재 동전을 뺀 값이 dp[j-coin[i]]를 의미합니다. 그래서 현재 거스름돈 dp[j]와dp[j-coin[i]]+1을 비교하여 작은 값이 답이 됩니다.

이제 5도 했으니 6도 해봅시다. 위의 식대로 구한다면 다음의 표가 완성되겠습니다.

6원 사용시

거스름 돈	동전 갯수(1원 갯수, 4원 갯수, 5원 갯수, 6원 갯수)
1	1(1,0,0,0)
2	2(2,0,0,0)
3	3(3,0,0,0)
4	1(0,1,0,0)
5	1(0,0,1,0)
6	1(0,0,0,1)
7	2(1,0,0,1)
8	2(0,2,0,0)
9	2(0,1,1,0)
10	2(0,0,2,0)
11	2(0,0,1,1)
12	2(0,0,0,2)
13	3(1,0,0,2)
14	3(0,1,2,0)

이제 모든 동전을 사용해서 14원이 3개의 동전으로 교환될 수 있다는 것을 알았습니다.

구현

구현은 뭐 위에서 설명한 것을 그대로 코드로 옮기면 되는데 몇몇 설명할게 아직은 남아있습니다. 전체 소스코드를 보면서 이야기 해보도록 하겠습니다.

#include <stdio.h>
#define MIN(a,b) a<b ? a:b
#define N 4
#define M 14
#define INF 987654321;
int dp[M+1];
int coin[N] = { 1,4,5,6 };
int main() {
	int i, j;

	for (i = 1; i <= M; i++)
		dp[i] = INF;

	for (i = 0; i < N; i++) {
		printf("동전 %d 사용시\n",coin[i]);
		for (j = coin[i]; j <= M; j++) {
			dp[j] = MIN(dp[j], dp[j - coin[i]] + 1);
			printf("%d %d\n", j, dp[j]);
		}
		printf("\n\n");
	}
	printf("%d\n", dp[M]);
}

우선 dp를 아주 큰 값으로 초기에 설정합니다. 그렇지 않으면 0이 되니까요. MIN 매크로 함수를 통해서 작은 값을 구해야하는데 dp가 0이 되버리면 MIN은 항상 0을 반환하게 됩니다.

위에서 이야기한대로 코드로 옮겼습니다.