[알고리즘] 백준 온라인 저지 BOJ 1463: 1로 만들기

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냄새가 나지 않습니까?

제약 조건

---

n은 1000000이하네요. O(n^2) 이상으로는 풀 수 없습니다.

풀이

---

 

세가지 조건과 메모이제이션을 이용해서 이 문제를 풀 수 있습니다. 

#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문 부분을 주석처리하여 제출해보세요. 결과는 맞지만 효율성에서 차이가 나는게 보일겁니다.