[1463] 1로 만들기

내 풀이

#include <iostream>

int dp[3000001];
int n;

int main(void) {
	scanf("%d", &n);
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	for (int i = 1; i <= n; i++) {
		if (dp[3 * i] == 0) {
			dp[3 * i] = dp[i] + 1;
		}
		else {
			dp[3 * i] = dp[3 * i] > dp[i] + 1 ?  dp[i] + 1 : dp[3 * i];
		}

		if (dp[2 * i] == 0) {
			dp[2 * i] = dp[i] + 1;
		}
		else {
			dp[2 * i] = dp[2 * i] > dp[i] + 1 ? dp[i] + 1 : dp[2 * i];
		}

		if (dp[1 + i] == 0) {
			dp[1 + i] = dp[i] + 1;
		}
		else {
			dp[1 + i] = dp[1 + i] > dp[i] + 1 ? dp[i] + 1 : dp[1 + i];
		}
	}
	printf("%d\n", dp[n]);
	return 0;
}

Top-Down

#include <iostream>
using namespace std;

int dp[1000001];
int n;

int go(int x) {
	if (x == 1) return 0;
	if (dp[x] > 0) return dp[x];
	dp[x] = go(x - 1) + 1;
	if (x % 3 == 0) {
		dp[x] = dp[x] > go(x/3)+ 1 ? go(x/3) + 1 : dp[x];
	}
	if (x % 2 == 0) {
		dp[x] = dp[x] > go(x / 2) + 1 ? go(x / 2) + 1 : dp[x];
	}
	return dp[x];
}

int main(void) {
	scanf("%d", &n);
	cout << go(n) << "\n";
	return 0;
}

Bottom-up

#include <iostream>

int dp[1000001];
int n;

int main(void) {
	scanf("%d", &n);
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + 1;
		if (i % 2 == 0) {
			dp[i] = dp[i] > dp[i / 2] + 1 ? dp[i / 2] + 1 : dp[i];
		}
		if (i % 3 == 0) {
			dp[i] = dp[i] > dp[i / 3] + 1 ? dp[i / 3] + 1 : dp[i];
		}
	
	}
	printf("%d\n", dp[n]);
	return 0;
}