백준 BOJ 1463번

---

접근 방법

 

생각보다 어렵지 않았다. 재귀로 모든 경우를 따져보면 된다.

다만 주의할 점은 재귀만 사용하면 시간 초과가 뜬다는 점이다. DP를 사용해서 시간을 아끼자.

---

코드

import java.util.*;

public class Main {
   static Integer dp[];
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      int N = in.nextInt();
      dp = new Integer[N+1];
      dp[0] = 0;
      dp[1] = 0;
      System.out.println(makeOne(N));
   }
   static int makeOne(int N){
      if(dp[N] == null){
         if(N % 6 == 0) 
            dp[N] = Math.min(makeOne(N-1), Math.min(makeOne(N/3), makeOne(N/2))) + 1;
         else if(N % 3 == 0)
            dp[N] = Math.min(makeOne(N/3), makeOne(N-1)) + 1;
         else if(N % 2 == 0) 
            dp[N] = Math.min(makeOne(N/2), makeOne(N-1)) + 1;
         else 
            dp[N] = makeOne(N-1) + 1;
      }
      return dp[N];
   }
}