BJ14631

package day0331;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class MakeOne {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int max_cnt = Integer.MAX_VALUE;
	static void func(int X, int cnt) {
		if(cnt >= max_cnt) {
			return;
		}
		if(X == 1 && cnt < max_cnt) {
			max_cnt = cnt;
		}
		if(X % 3 == 0) func(X / 3, cnt + 1);
		if(X % 2 == 0) func(X / 2, cnt + 1);
		func(X - 1, cnt + 1);
	}
	public static void main(String[] args) throws IOException {
		int X = Integer.parseInt(br.readLine());
		/*func(X, 0);
		bw.append(max_cnt + "");
		bw.flush();
		*/
		int[] DP = new int[X + 1]; // DP 테이블

        for (int i = 2; i <= X; i++) {
            int min = 1 + DP[i - 1];
            if (i % 3 == 0 && 1 + DP[i / 3] < min) min = 1 + DP[i / 3];
            if (i % 2 == 0 && 1 + DP[i / 2] < min) min = 1 + DP[i / 2];
            DP[i] = min;
        }

        System.out.println(DP[X]);
	}
}