[JAVA] 백준 1463_1로 만들기

 

[문제 링크]

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

 

 

📌 문제 탐색하기

 

 

📌 가능한 시간복잡도 

 

 

📌 코드 설계하기

1. 정수 N 입력받기

2. 

 

📌 정답 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        
        int[] dp = new int[N + 1];
        
        dp[1] = 0; 
        
        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]);
    }
}