백준 1463번 - 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

예를 들면 4의 경우 2로 나눌 수도 있고 -1을 해서 최솟값을 찾을 수 있다.

그렇게 되면  (2의 최솟값, 3의 최솟값) 중에서 최솟값을 찾아 +1 을 하면 그 숫자의 최솟값을 구할 수 있다.

 

5의 경우의 수

4의 최솟값+1

 

6의 경우의 수

( 5의 최솟값, 2의 최솟값, 3의 최솟값 ) 중 최솟값 +1

 

7의 경우의 수

6의 최솟값+1

 

8의 경우의 수

7의 최솟값+1

 

...

 

 

코드

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
	       Scanner sc = new Scanner(System.in);
	       int num = sc.nextInt();
	       int dp[] = new int[num+1];
	       dp[0]=dp[1]=0;
	      
	       for(int i=2;i<=num;i++)
	       {
	    	   dp[i]=dp[i-1]+1;
	    	   if(i%2==0)
	    	   {
	    		   dp[i]=Math.min(dp[i], dp[i/2]+1);
	    	   }
	    	   if(i%3==0)
	    	   {
	    		   dp[i]=Math.min(dp[i], dp[i/3]+1);
	    	   }
	       }
	       System.out.println(dp[num]);
	}
}