'동적 계획법'에 해당되는 글 2건

동전 교환 알고리즘

개념

현실에서는 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원 사용시

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

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

4원 사용시

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

5원 사용시

이제 감이 오시나요?

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

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

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

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

6원 사용시

이제 모든 동전을 사용해서 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]);
}

1463번 1로 만들기

문제 해석

문제는 너무 간단 합니다. 세가지 규칙이 있는데요.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

이렇게 만들어서 1로 만들어라 이겁니다. 12를 최소로 위 규칙을 사용하면 어떤 과정을 거칠 수 있을까요?

12 - 4(1번 규칙 적용) - 2(2번 규칙 적용) - 1(2번 또는 3번 규칙 적용)

이렇게 3번으로 1을 만들 수 있다는 건데요. 

36은 어떻게 구할 수 있을까요?

36 - 12(1번 규칙 적용)

12는 위에서 구했습니다. 감이 오시죠? DP냄새가 나지 않습니까?

#include <cstdio>
#include <string.h>

#define min(x,y) x<=y ? x:y
#define INF 987654321
using namespace std;

int dp[1000001];

int solve(int n) {

	if (n == 1) return 0;
	if (dp[n] != -1) return dp[n];

	int ret = INF;
	if (n % 2 == 0) ret = 1 + solve(n / 2);
	if (n % 3 == 0) ret = min(ret, 1 + solve(n / 3));
        //ret = min(ret, 1+solve(n-1));
	if (n % 6 != 0) 
		ret = min(ret, 1 + solve(n - 1));

	return dp[n] = ret;
}

int main() {

	int n;
	scanf("%d", &n);

	memset(dp, -1, sizeof(dp));
	printf("%d\n", solve(n));
}

n을 규칙대로 3으로 나누어 떨어지면 3으로 나누고, 2로 나누어 떨어지면 2로 나누고, 또는 1을 뺀 규칙을 적용해서 1로 만들어보는 것입니다. 3으로 나누어 떨어지지 않거나, 2로 나누어 떨어지지 않을 땐 1을 빼는 규칙을 적용해줍니다.

왜요?

n을 1로 만들어주는데 있어서 2와 3으로 나누는 것이 유리하다는 것이죠. 어떤 수로 나누는 것이 n을 줄이는 일에 효과적이라는 겁니다. 그래서 1을 최소로 빼주고 될 수 있으면 2와 3으로 나누는 편이 더 좋습니다.  그러니 2와 3의 최소 공배수 6을 이용해서 6으로 나누어 떨어지지 않으면 1을 빼는 것을 시도하는 것입니다.

위 코드의 주석을 해제하고 if문 부분을 주석처리하여 제출해보세요. 결과는 맞지만 효율성에서 차이가 나는게 보일겁니다.