1) DP 점화식 정의
DP[x]를 x가 1이 되기 위한 최소 연산 횟수로 정의합니다.
따라서 DP[1]은 0이 되고 (초기값), dp[x]는 dp[x - 1] + 1; 입니다. (기본)
하지만, x가 2로 나누어 떨어지면, dp[x - 1] + 1, dp[x / 2] + 1중 최솟값을,
x가 3으로 나누어 떨어지면, dp[x - 1] + 1, dp[x / 3] + 1중 최솟값을 고릅니다.
그리고 dp[n]을 출력합니다.
2) source code
#define ll long long
#define pii pair<int, int>
#define mod 10000007
#define INF 100000000
#define pb push_back
#define pi 3.141592
using namespace std;
int dp[1010101];
int main(void){
ios_base::sync_with_stdio(false);
cout.tie(0);
cin.tie(0);
int n;
cin >> n;
dp[1] = 0;
for(int i = 2; i <= n; i++){
dp[i] = dp[i - 1] + 1;
if(i % 2 == 0){
dp[i] = min(dp[i], dp[i / 2] + 1);
}
if(i % 3 == 0){
dp[i] = min(dp[i], dp[i / 3] + 1);
}
}
cout << dp[n];
return 0;
}