[Baekjoon Online Judge] 1463번: 1로 만들기

1463번: 1로 만들기

요구사항

 - 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다.

  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

  2. X가 2로 나누어 떨어지면, 2로 나눈다.

  3. 1을 뺀다.

 - 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 쵯솟값을 출력한다.

입력

 - 첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.

출력

 - 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

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

public class Baekjoon1463 {
    static int[] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        String input = bufferedReader.readLine();
        int n = Integer.parseInt(input);

        dp = new int[n + 4];

        for (int i = 0; i < dp.length; i++) {
            divide(i);
        }

        bufferedWriter.write(String.valueOf(dp[n]));

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }

    private static int divide(int n) {

        if (n == 0 || n == 1) {
            dp[n] = 0;
        } else if (n == 2 || n == 3) {
            dp[n] = 1;
        } else if (n % 2 == 0 && n % 3 == 0) {
            int temp1 = Math.min(dp[n / 3] + 1, dp[n / 2] + 1);
            int temp2 = dp[n - 1] + 1;

            dp[n] = Math.min(temp1, temp2);
        } else if (n % 2 == 0) {
            dp[n] = Math.min(dp[n / 2] + 1, dp[n - 1] + 1);
        } else if (n % 3 == 0) {
            dp[n] = Math.min(dp[n / 3] + 1, dp[n - 1] + 1);
        } else {
            dp[n] = dp[n - 1] + 1;
        }

        return dp[n];
    }
}

 

 조건에 맞는 dp 테이블에 중간 값을 저장하였고, for 루프를 돌며 dp 테이블을 채워나갔다. 마지막에 dp[n]을 출력하여 마무리하였다. dp 테이블의 크기를 4 이상 늘려준 이유는 초기에 n 값이 0, 1, 2, 3 일 때 값을 미리 채워두기 위한 용도이다.