5가지 모두 “top-bottom” 방식으로 풀었는데, 다소 비효율적이다. “bottom-top”방식으로 접근한 코드가 최상단 c++코드인데, 작은 수 부터 구성한다면, 이런 점화식으로 올라갈 수 있다.

• d 배열의 값은 index의 숫자까지 1에서 부터 오기위한, 최소 횟수를 의미한다.
• d[n] = 1부터 n이 되기위한, 최소 횟수
• d[n-1] = n -> n-1로 만들때, “1빼기” 연산이 1회 수행되므로,
  n-1까지 수가 만들어지는 횟수에 1만 더하면 된다.
• d[n/2]: d[n] = d[n/2] + 1 의 의미도 동일하게, d[n/2]까지의 횟수에서, 2를 곱하는 횟수 1번만 더하면 된다.

이런식으로 배열을 모두 채워가면, bottom-top으로 모든 수들을 구할 수 있다.

C++ 코드(bottom-top)

#include <iostream>
using namespace std;

int d[1000001];		//10의 6승이므로, 해당 배열 생성

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

	for (int i = 2; i <= n; i++) {
		int v = d[i - 1] + 1;
		if (i % 2 == 0) v = min(v, d[i / 2] + 1);
		if (i % 3 == 0) v = min(v, d[i / 3] + 1);
		d[i] = v;
	}

	cout << d[n];

}

C++ 코드(top-bottom)

#include <iostream>
using namespace std;

int dp(int x, int count, int& min) {

	//1. base check
	if (x == 1) {
		if (count < min) min = count;
		return x;
	}

	//2. memoization
	count++;

	//3. recurrence relation
	if (x % 3 == 0) {
		if (count >= min) return x;
		else dp(x / 3, count, min);
	}
	if (x % 2 == 0) {
		if (count >= min) return x;
		else dp(x / 2, count, min);
	}
	if (count >= min) return x;
	else dp(x - 1, count, min);

	return x;

}


int main() {

	int x = 0;
	scanf("%d", &x);
	int count = 0;
	int m = 1000000;
	dp(x, count, m);

	printf("%d", m);
}
}


int main() {

	int N;
	scanf("%d", &N);
	printf("%d", dp(N));
}

C# 코드

using System.Text;
using static System.Console;

class Program
{
    static int min = 1000000;
    static void dp(int x, int count)
    {
        if( x <= 1)
        {
            if (count < min) min = count;
            return;
        }
        count++;

        if (count >= min) return;
        if (x % 3 == 0) dp(x / 3, count);
        if (x % 2 == 0) dp(x / 2, count);
        dp(x - 1, count);

        return;
    }
    public static void Main(string[] args)
    {
        int input = int.Parse(ReadLine());
        dp(input, 0);
        WriteLine(min);
    }
}

Java 코드

import java.util.*;

public class Main {

    static int min = 1000000;
    static void dp(int x, int count){
        if(x <= 1){
            if(count < min) min = count;
            return;
        }

        if(x % 3 == 0){
            if( count > min ) return;
            dp(x/3, count+1);
        }
        if(x % 2 == 0){
            if(count > min) return;
            dp(x/2, count+1);
        }
        if(count> min) return;
        dp(x-1, count+1);

        return;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int input = s.nextInt();
        dp(input, 0);
        System.out.println(min);


    }

}

Kotlin 코드

import java.util.*

fun main(args: Array<String>){
    val s = Scanner(System.`in`)
    val input = s.nextInt()
    var min = 1000000

    fun dp(x: Int, count : Int){
        if(x <= 1){
            if(count< min) min = count
            return
        }

        if(x % 3 == 0) {
            if(count > min) return
            dp(x/3, count+1)
        }
        if(x % 2 == 0) {
            if(count > min) return
            dp(x/2, count+1)
        }
        if(count > min) return
        dp(x-1, count+1)

        return
    }

    dp(input, 0)

    print(min)


}

Python 코드

import sys
sys.setrecursionlimit(300000)       #파이썬은 재귀를 1000회만 기본으로 함으로, 제한을 늘려놓기
min =1000000

def dp(x, count):
    global min          #파이썬은 전역변수를 global로 설정해줘야 지역내에서 사용이 가능.
    if x <= 1:
        if count < min: min = count
        return

    count+=1

    if x % 3 == 0:
        if count >= min: return
        dp(x/3, count)
    if x % 2 == 0:
        if count >= min: return
        dp(x/2, count)
    if count >= min: return
    dp(x-1, count)

    return

x = int(input())
dp(x, 0)
print(min)