[백준알고리즘] 1로 만들기 (DP)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException{ BufferedReader reader=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(reader.readLine()); memo=new int[n+1]; Arrays.fill(memo, -1); System.out.println(dp(n)); } static int memo[]; static int dp(int n){ if(n==1) return 0; //n==1일때는 연산이 필요 없다. //if(n==0) return 0; if(memo[n]!=-1) return memo[n]; int count1=dp(n-1)+1;//연산시 +1 int count2=Integer.MAX_VALUE;//3의 배수가 아닐때 count2=0으로 하면 min이 0이됨... int count3=Integer.MAX_VALUE;//위와같음... if(n%3==0) count2= dp(n/3)+1;//연산시 +1 if(n%2==0) count3= dp(n/2)+1;//연산시 +1 return memo[n]=Math.min(Math.min(count1, count2), count3); } }