백준 1463. 1로 만들기 :: 돼지개발자

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

"DP DP 딥"

1을 가지고 N을 만든다고 역으로 생각하자. 

dp[3] 까지 최소값을 구한다. 1이 되겠다. 그 이후에 4를 만드려면 어떤 방법이 있을까? 2 에서 2를 곱하거나 3에서 더하기 1을 하거나.

              dp[n/2] + 1 ( n % 2 == 0 )

dp[n] =    dp[n/3] + 1 ( n % 3 == 0 )

              dp[n-1]

이중에 최소값을 dp[n]으로 한다.

import java.util.Scanner;
 
public class Main {
 
    static int n;
    static int[] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dp = new int[n+1];
        
        if(n == 1) {
            System.out.println(0);
            return;
        }
        else if ( n == 2) {
            System.out.println(1);
            return;
        }
        else if (n == 3) {
            System.out.println(1);
            return;
        }
        
        // dp값 초기화
        dp[2] = dp[3] = 1;
        
        for (int i = 4; i <= n; i++) {
            int min = dp[i-1];
            
            if(i % 2 == 0) {
                min = Math.min(min, dp[i/2]);
            }
            
            if(i % 3 == 0) {
                min = Math.min(min, dp[i/3]);
            }
            
            dp[i] = min + 1 ;
        }
        System.out.println(dp[n]);
    }
}