백준1463과 에러

문제 링크

백준 1463

Solved.ac 티어

🥈실버 3

문제 풀이 및 힌트

⬛피보나치와 같은 메모제이션을 사용하여 메모리 관리
메모제이션의 설명과 예시
때로는 2나 3으로 나눌 수 있어도 1을 우선 빼는 게 가성비가 좋을 수도 있다
ex)10의 경우 2로 나누어떨어지나 우선 1을 빼서 9로 만들어야 최적의 해가 나온다

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 10e6 + 1;
int dp[MAX];
int solve(int n) {
	if (n == 1)return 0;
	if (dp[n] != 0)return dp[n];
	dp[n] = solve(n - 1) + 1;
	if (n % 3 == 0) dp[n] = min(dp[n], solve(n / 3) + 1);
	if (n % 2 == 0) dp[n] = min(dp[n], solve(n / 2) + 1);
	return dp[n];
}
int main() {
	ios_base::sync_with_stdio(false);
	int n = 0;
	cin >> n;
	dp[2] = 1;
	dp[3] = 1;
	cout << solve(n);
	return 0;
}