백준 Java | 백준 1463번 1로 만들기 (DP)

1463번: 1로 만들기 (acmicpc.net)

1463번: 1로 만들기

 

Bottom-up 방식으로 DP 배열을 완성해주었다. 

package DP.P1463;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N;
    static int[] DP;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        // i번째 값 = i를 1로 만드는 데 필요한 연산 횟수 최솟값
        DP = new int[N+1];

        if (N==1){
            System.out.println(0);
            return;
        }
        for (int i=1;i<N+1;i++){
            // X에 사용할 수 있는 연산은 다음 세 가지
            if (i==2||i==3){
                DP[i] = 1;
                continue;
            }
            int candidate = DP[i-1]+1;
            if (i%3==0){
                candidate = Math.min(DP[i/3]+1, candidate);
            }
            if (i%2==0){
                candidate = Math.min(DP[i/2]+1, candidate);
            }
            DP[i] = candidate;
        }
        System.out.println(DP[N]);
    }
}