[백준]1로 만들기 - 복습

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

각 단계별 3가지 경우의 수가 있으니
10^6 숫자를 전역탐색하기에는 시간이 부족하다

1을 만드는게 목적이니
1에서부터 3가지 방법을 사용하면서 값을 만들면서
최소 횟수만 남겨서 기록한다

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

int N;
int cache[1000001];

void solve(int x)
{
    if (x > N) return;

    int& ret = cache[x];

    ret = cache[x - 1] + 1;
    if (x % 2 == 0)
        ret = min(ret, cache[x / 2] + 1);
    if (x % 3 == 0)
        ret = min(ret, cache[x / 3] + 1);

    solve(x + 1);
}


int main()
{
    cin >> N;
    memset(cache, -1, sizeof(cache));
    cache[1] = 0;
    solve(1);

    /*for (int i = 1; i <= N; i++)
    {
        cout << cache[i] << " ";
    }cout << endl;
*/
    cout << cache[N] << endl;
}