240228_TIL

백준 1463 1로 만들기

package Baekjoon;

import java.util.Scanner;

public class B1463 {

	static Integer[] a;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		 
		int N = in.nextInt();
 
		a = new Integer[N + 1];
		a[0] = a[1] = 0;
 
		System.out.print(recur(N));
	}
	
	static int recur(int N) {
		 
		if (a[N] == null) {
			// 6으로 나눠지는 경우 
			if (N % 6 == 0) {
				a[N] = Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 1;
			}
			// 3으로만 나눠지는 경우 
			else if (N % 3 == 0) {
				a[N] = Math.min(recur(N / 3), recur(N - 1)) + 1;
			}
			// 2로만 나눠지는 경우 
			else if (N % 2 == 0) {
				a[N] = Math.min(recur(N / 2), recur(N - 1)) + 1;
			}
			// 2와 3으로 나누어지지 않는 경우
			else {
				a[N] = recur(N - 1) + 1;
			}
		}
		return a[N];
	}

}