[백준1463] 1로 만들기 (다이나믹 프로그래밍) (C++)

BOJ 바로가기

정답 소스코드를 보고 수정한 코드

#include <iostream>
using namespace std;
int memo[1000001] = { 0 };
int route(int);
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int x;
	cin >> x;
	cout<<route(x);
	return 0;
}
int route(int n) {
	if (n == 1) return 0;
	if (memo[n] > 0) return memo[n];
	memo[n] = route(n-1) + 1;
	if (n % 2 == 0) {
		int temp = route(n/2) + 1;
		if (memo[n] > temp) memo[n] = temp;
	}
	if (n%3 == 0) {
		int temp = route(n/3) + 1;
		if (memo[n] > temp) memo[n] = temp;
	}
	return memo[n];
	}

수정 전 코드

#include <iostream>
using namespace std;
int memo[1000001] = { 0 };
int route(int);
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int x;
	cin >> x;
	cout<<route(x);
	return 0;
}
int route(int x) {
	memo[1] = 0;
	if (memo[x]) // 저장된 값이 있으면 그대로 return;
		return memo[x];
	int a = 0, b = 0;
	if (x % 3 == 0)
		a = x / 3;
	if (x % 2 == 0)
		b = x / 2;
	if ((a != 0) && (b != 0)) { // x가 3과 2로 모두 나누어떨어진다면
		if (route(a) < route(b)) {
			if (route(x - 1) < route(a)) {
				memo[x] = route(x - 1) + 1;
			}
			else {
				memo[x] = route(a) + 1;
			}
		}
		else {
			if (route(x - 1) < route(b)) {
				memo[x] = route(x - 1) + 1;
			}
			else {
				memo[x] = route(b) + 1;
			}
		}
	}
	else if (a != 0) { // x가 3으로 나누어떨어진다면
		if (route(a) > route(x - 1)) {
			memo[x] = route(x - 1) + 1;
		}
		else {
			memo[x] = route(a) + 1;
		}
	}
	else if (b != 0) { // x가 2로 나누어떨어진다면
		if (route(x - 1) < route(b)) {
			memo[x] = route(x - 1) + 1;
		}
		else {
			memo[x] = route(b) + 1;
		}
	}
	else if (x != 1) { // x가 2 또는 3으로 나누어떨어지지 않는다면
		memo[x] = route(x - 1) + 1;
	}
	return memo[x];
}

최솟값을 구할 때 값을 일일이 비교하는 코드보다는 min을 초기화해두고 하나씩 덧붙이면서 비교해주는 방식이 훨씬 간편하다.