[Java] 백준 1463 - 1로 만들기

Baekjoon_1463 - 1로 만들기

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

문제

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

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

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

입력

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

출력

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

---

해결방법

• DP를 이용해서 해결한다.
  • 연산 횟수를 반환하는 cal() 함수의 재귀를 이용한다.
  • n 이 6으로 나눠질 때 (2와 3 모두로 나눠질 때)
    • cal(n - 1) , cal(n / 3), cal(n / 2) 중 최솟값에 1을 더하면 현재의 연산 횟수인 dp[n]이 된다.
  • n 이 3으로만 나눠질 때
    • cal(n - 1), cal(n / 3) 중 최솟값에 1을 더하면 현재의 연산 횟수인 dp[n]이 된다.
  • n 이 2로만 나눠질 때
    • cal(n - 1), cal(n / 2) 중 최솟값에 1을 더하면 현재 연산 횟수인 dp[n]이 된다.
• 위의 연산은 모두 dp[n] 이 비어있을 때 해야 하므로 dp 배열은 int가 아닌 Integer로 받아서 null인지 아닌지 판단한 후 계산한다.

코드

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

public class Baekjoon_1463 {
    static Integer[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        dp = new Integer[n + 1];
        dp[1] = 0;
        dp[0] = 0;

        System.out.println(cal(n));
    }

    public static int cal(int n) {
        if (dp[n] == null) {
            if (n % 6 == 0) {
                dp[n] = Math.min(cal(n - 1), Math.min(cal(n / 3), cal(n / 2))) + 1;
            } else if (n % 3 == 0) {
                dp[n] = Math.min(cal(n / 3), cal(n - 1)) + 1;
            } else if (n % 2 == 0) {
                dp[n] = Math.min(cal(n / 2), cal(n - 1)) + 1;
            } else {
                dp[n] = cal(n - 1) + 1;
            }
        }
        return dp[n];
    }
}

재귀함수를 호출하는 순서도 중요하다.

위의 if 문에서 cal(n / 3) 보다 cal(n - 1) 을 먼저 호출하게 되면 시간 초과가 나게 되는데, cal(n - 1) 을 먼저 호출하게 되면 1부터 n-1까지 모두 일단 계산해버리기 때문이다. 따라서 cal(n / 3) 이나 cal(n / 2) 로 적절하게 dp 배열값을 계산해놓은 후, cal(n- 1) 을 해야 불필요한 계산이 줄어든다.