[C++/백준 1463번] 1로 만들기

 

 

 

초기화 할 때 fill 을 사용해야 확실하게 초기화 할 수 있다.

경우의 수를 나눈 다음 재귀를 활용해 풀이했다.

#include <iostream>
#include <algorithm>
using namespace std;
int arr[1000001] ;

int div(int input)
{
    if(arr[input] == -1)
    {
        if(input % 6 == 0)
        {
            arr[input] = min({div(input-1), div(input/3), div(input/2)}) + 1;
        }
        else if (input % 3 == 0)
        {
            arr[input] = min({div(input-1), div(input/3)}) + 1;
        }
        else if (input % 2 == 0)
        {
            arr[input] = min({div(input-1), div(input/2)}) + 1;
        }
        else
            arr[input] = div(input-1)+ 1;

    }

    return arr[input];

}

int main() {

    int N;

    cin >> N;

    fill(arr, arr + 1000001, -1);
    arr[0] = arr[1] = 0;

    cout << div(N);


    return 0;
}