[BOJ 1463] 1로 만들기 (Java, DP)

 

 

---

문제 링크

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

1463번: 1로 만들기

---

문제 풀이

- 상향식(Bottom-up)으로 DP 풀이

- 시간복잡도 O(N)

 

*DP 배열 결과

idx	0	1	2	3	4	5	6	7	8	9	10
DP	0	0	1	1	2	3	2	3	3	2	3

---

제출 코드

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

public class Main {
    
    static int N;

    static int[] DP;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
    }

    static void pro() {
        DP = new int[N + 1];
        for(int i = 2; i <= N; 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[N]);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}