[백준] 온라인 저지 1463번 : 정수를 1로 만들기(Java), DP

점화식부터 세워보자.

 

D[i]를 i에서 1을 만드는 데 걸리는 최소 연산 횟수라고 가정하고 D[10]을 구해보자.

우선 D[1] ~ D[9]는 알고 있다고 가정했을 때,

"D[10] = D[9] + 1" 이 됨을 알 수 있다. -> D[10]에서 -1 연산을 한번 더 수행하면 되기 때문

또한 "D[10] = D[5] + 1" 가 됨을 알 수 있다. -> D[10]에서 /2 연산을 한번 더 수행하면 되기 때문

 

 

 

문제 풀이

import java.util.Scanner;

public class P1463_1로만들기 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] D = new int[N+1];

        D[1] = 0; // 초기 셋팅 : 1이 1이 되는데 필요한 연산 수는 0

        for(int i=2; i<=N; i++) {
            D[i] = D[i-1] + 1;
            if(i % 2 == 0) {
                D[i] = Math.min(D[i], D[i/2] + 1);
            }
            if(i % 3 == 0) {
                D[i] = Math.min(D[i], D[i/3] + 1);
            }
        }
        System.out.println(D[N]);
    }
}