BOJ)1463 1로 만들기

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

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define INF 9999999

int dp[1000001]; : Memoization
 
void divide(int x, int cnt) {
    if (dp[x] < cnt) return;
    if (cnt != 0)dp[x] = min(dp[x], cnt);
    if (x == 1) return;
Overlapping : 
    if (x % 3 == 0) divide(x / 3, cnt + 1);
    if (x % 2 == 0) divide(x / 2, cnt + 1);
    divide(x - 1, cnt + 1);
}
 
int main()
{
    int t;
    cin >> t;
    memset(dp, INF, sizeof(dp));
    divide(t, 0);
    cout << dp[1];
}