문제

점화식을 세워 동적으로 푸는 문제
한 숫자가 정해지면 갈 수 있는 갈래는 최대 3갈래

Idea

계산된 내용은 global하게 선언된 vector에 입력하고, 만약 해당 값이 없는 경우만 Recursive하게 계산

Code

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

#include <iostream>
#include <vector>

constexpr int MAX_N = 1000000;

std::vector<int> gVector(MAX_N, 0);

int MakeOne(const int N){
    if (N==1){
        return 0;
    }
    else if (N<=3){
        return 1;
    }
    
    int answer = MakeOne(N-1)+1;
    if (N%2==0){
        int temp = 0;
        if (gVector[N/2] > 0){
            temp = gVector[N/2];
        }
        else{
            temp = MakeOne(N/2);
        }
        answer = std::min(answer, temp+1);
    }

    if (N%3==0){
        int temp = 0;
        if (gVector[N/3] > 0){
            temp = gVector[N/3];
        }
        else{
            temp = MakeOne(N/3);
        }
        answer = std::min(answer, temp+1);
    }

    gVector[N] = answer;

    return answer;
}

int main(){
    int N = 0;
    std::cin >> N;

    std::cout << MakeOne(N) << std::endl;

    return 0;
}

Reference

https://beginnerdeveloper-lit.tistory.com/81