백준 온라인 저지(Baekjoon Online Judge) - 1463 : 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

#include <iostream>
#include <cstring>
using namespace std;

const int MAX = 1000001;
int dp[MAX];
int memo[MAX];

int makeOne(int n) {
    if (n == 1) return 0; // 기저 조건

    // memoization
    if (memo[n] != -1) return memo[n];

    // dp 점화식
    dp[n] = makeOne(n - 1) + 1;
    if (n % 2 == 0) dp[n] = min(dp[n], makeOne(n / 2) + 1);
    if (n % 3 == 0) dp[n] = min(dp[n], makeOne(n / 3) + 1);

    memo[n] = dp[n]; // memoization
    return dp[n];
}

int main() {
    int n;
    cin >> n;

    memset(memo, -1, sizeof(memo)); // memoization 배열 초기화
    cout << makeOne(n) << '\n';

    return 0;
}