1463 1로 만들기

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
public class main {
	static int N;
    static int answer=Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
       	N = Integer.parseInt(br.readLine());
       	dp(N,0);
       	
   		bw.write(answer+" ");
    	bw.flush();
    	bw.close();
    }
	static void dp(int n, int count) {
		if(n==1) {
			answer = Math.min(answer,count);
			return;
		}
		if(count >= answer) return;
		
		if(n%3==0) {
			dp(n/3,count+1);
		}
		if(n%2==0) {
			dp(n/2,count+1);
		}
		dp(n-1,count+1);
	}
}

제일 먼저 떠오른게 함수만들어서 재귀로 count 1씩 증가시키면서 넘겨주는 거 였는데

오래걸릴 거라고 생각했다 힝

count가 answer 보다 크면 return 하는 이유는 

count의 최대의 경우는 n-1 이기 때문 ~ 즉,,하나도 나누지 않고 1씩 다빼주는 경우