[백준 1463] 1로 만들기 (JAVA)

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

1463번: 1로 만들기

정수 n 을 1로 만들기 위한 연산 횟수의 최솟값을 dp[n] 이라고 가정하자. 

 

그러면 dp[0] = dp[1] = 0, dp[2] = 1, dp[3] = 1

 

dp table 을 아래와 같이 bottom-up 방식으로 채워나갈 수 있다.

 

1. N 에 대하여 N-1 이 가능하다면 dp[n] = dp[n-1]+1

2. N 이 2로 나누어 떨어지면 dp[n] 은 dp[n/2]+1 와 dp[n-1]+1 중 더 작은 값을 선택

3. N 이 3으로 나누어 떨어지면 dp[n] 은 dp[n/3]+1 와 dp[n-1]+1 중 더 작은 값을 선택

 

import java.io.FileInputStream;
import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[1000001];
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;
        dp[3] = 1;
        for(int i = 4 ; i<=n ; i++){
            dp[i] = dp[i-1]+1;
            if(i%3==0){
                dp[i] = Math.min(dp[i/3]+1, dp[i]);
            }
            if(i%2==0){
                dp[i] = Math.min(dp[i/2]+1, dp[i]);
            }
        }
        System.out.println(dp[n]);
    }
}