[백준] 1463번 1로 만들기

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

1463번: 1로 만들기

 

다이나믹 프로그래밍 : 점화식을 찾아 이전까지의 계산값을 배열에 저장

 

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        // (x - 1) + 1, (x / 2) + 1, (x / 3) + 1

        int[] dp = new int[N + 1];
        dp[0] = 0;
        dp[1] = 0;

        for(int i = 2; i <= N; i++) {
            // i에 이전까지의 dp값 저장
            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[N]);
    }

}