[BOJ] 1463. 1로 만들기

DP로 푸는 문제이다.n

처음에 문제를 보았을 때, 재귀를 이용하여 접근하였다. 하지만 재귀를 시간초과가 발생하였다. 그래서 DP를 이용하여 풀어보았다. bottom-up 방식을 이용하여 1부터 N까지 갈수있도록 하였다. 이 과정은 시간복잡도가 n이므로 금방 구할수 있었다. 즉, dp[n]= min(dp[n/3], dp[n/2], dp[n-1]) +1 이라는 점화식을 이용하여 풀었다.

package boj.base;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main_bj_1463_1로만들기 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        
        if(N==1 || N==2) {
            System.out.println(N-1);
            return;
        }
        
        int[] dp= new int[N+1];
        
        dp[1]=0;
        dp[2]=1;
        dp[3]=1;
        
        for(int i=4;i<=N;i++) {
            if(i%3==0 && i%2==0) {
                dp[i]=Math.min(dp[i/3]+1, Math.min(dp[i/2]+1, dp[i-1]+1));
            }else if(i%3==0) {
                dp[i]=Math.min(dp[i/3]+1, dp[i-1]+1);
            }else if(i%2==0) {
                dp[i]=Math.min(dp[i/2]+1, dp[i-1]+1);
            }else {
                dp[i]=dp[i-1]+1;
            }
        }
        
        System.out.println(dp[N]);
        
    }
}