12852 1로 만들기 2

시간 제한이 0.5초로 짧기 때문에 Bottom Up으로 푼 문제이다.

선택한 이유는, Top Down은 함수 호출로 인해 오버헤드가 상대적으로 크기 때문이다.

접근

최소 연산 수 구하기

잘 생각해보면 문제에 중복된 부분 문제들이 있다는걸 알 수 있다.

다이나믹 프로그래밍 관점에서 보자.

문제에선 1로 만들기 위한 최소 연산 수를 구하라고 되어 있지만, 거꾸로 1에서 X를 만들기 위한 최소 연산 수도 같은 방식이다. 점화식은 다음과 같다.

dp[n] = 1에서 n을 만들기 위한 최소 연산 수

dp[n] = min(dp[n / 3] + 1, dp[n / 2] + 1, dp[n - 1] + 1)

for (int i = 1; i <= X; i++) {
		if (i * 3 <= X && dp[i * 3] > dp[i] + 1) {
			dp[i * 3] = dp[i] + 1;
		}
		if (i * 2 <= X && dp[i * 2] > dp[i] + 1) {
			dp[i * 2] = dp[i] + 1;
		}
		if (i + 1 <= X && dp[i + 1] > dp[i] + 1) {
			dp[i + 1] = dp[i] + 1;
		}
	}

경로 구하기

경로를 위한 배열을 만들고, 다음 n을 계산했을 때 값을 초기화할 수 있으면 지금 경로를 저장한다.

또한 경로를 출력하는건 재귀형태가 간단하기 때문에 재귀를 사용하였다.

path[x * 3] = path[x]

 

정답코드 (Bottom Up)

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_SIZE 1000001
#define INF 987654321
int X;
int dp[MAX_SIZE] = { 0, };
int path[MAX_SIZE] = { 0, };
void track(int s)
{
	printf("%d ", s);
	if(s != 1)
		track(path[s]);
}
void BottomUp()
{
	dp[1] = 0;
	for (int i = 1; i <= X; i++) {
		if (i * 3 <= X && dp[i * 3] > dp[i] + 1) {
			dp[i * 3] = dp[i] + 1;
			path[i * 3] = i;
		}
		if (i * 2 <= X && dp[i * 2] > dp[i] + 1) {
			dp[i * 2] = dp[i] + 1;
			path[i * 2] = i;
		}
		if (i + 1 <= X && dp[i + 1] > dp[i] + 1) {
			dp[i + 1] = dp[i] + 1;
			path[i + 1] = i;
		}
	}
	printf("%d\n", dp[X]);
	track(X);
}
int main()
{
	fill(&dp[0], &dp[MAX_SIZE], INF);
	scanf("%d", &X);
	BottomUp();
	return 0;
}