<Algorithm> 13. 1463번 1로 만들기

1. 1463번 1로 만들기

• DP 방식 (  DP = 3개의 방법 중 가장 최소값  )

• Bottom-Up으로 초기값 설정이 중요

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

import java.util.Scanner;   public class Main {              public static void main(String[] args) {         Scanner sc=new Scanner(System.in);         int N=sc.nextInt();         int[] dp=new int[1000001];                  dp[1]=0;         dp[2]=1;         dp[3]=1;                  for(int i=4;i<=N;i++) {                          int min=dp[i-1]+1;             dp[i]=min;                          if(i%2==0) {                 int temp=dp[i/2]+1;                 if(min>temp) {                     min=temp;                     dp[i]=temp;                 }             }             if(i%3==0) {                 int temp=dp[i/3]+1;                 if(min>temp) {                     dp[i]=temp;                 }             }                         }                  System.out.println(dp[N]);     } } Colored by Color Scripter

cs