[BOJ/Java] 1463: 1로 만들기

문제

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

정수 `X`에 사용할 수 있는 연산은 세 가지가 있다.

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

정수 N이 주어지면, 위의 세 가지 연산을 적절히 사용해서 1을 만들 수 있는 최소 연산 횟수를 구해야 한다.

• 1 ≤ `N` ≤ 1,000,000

 

 풀이

시간 제한이 0.15초로 매우 짧고, `N`의 범위를 보았을 때 브루트 포스 알고리즘을 적용하기 어렵다는 것을 알 수 있다.

해당 문제는 DP(혹은 BFS)로 풀 수 있다. `N`이 10만 정도라면 DP로도 충분하다. 더 커지면 BFS를 사용할 수 있다.

 

`dp[i]`를 정수 `i`에서 1로 만들기 위한 최소 연산 횟수로 정의한다.

사용할 수 있는 모든 연산을 사용했을 때의 최솟값이 `dp[i]`가 된다.

1. `i - 1`
2. `i / 2`
3. `i / 3`

`i`에서 한 번 연산을 하고, 그 결과값에 대한 최소 연산 횟수를 dp라면, `dp[i] = 그 결과값의 dp + 1`로 계산할 수 있다.

1은 아무 연산을 사용하지 않고도 1로 만들 수 있으므로, 초기값인 `dp[1]`은 0이 된다.

2는 2로 한 번 나누거나, 1을 빼면 1로 만들 수 있으므로 `dp[2]`는 1이다. `dp[2]`는 `dp[1]`에서 1을 더하는 경우의 수와 2로 나누는 경우의 수 중 최솟값(둘 다 1)이 된다.

🔹 dp[2]

• 2를 1로 만드는 방법:
  • 2 → 1 (1을 빼기) → `dp[1] + 1` = 0 + 1 = 1
  • 2 → 1 (2로 나누기) → `dp[1] + 1` = 0 + 1 = 1
• 둘 중 작은 값은 1 → `dp[2]` = 1

3은 1을 두 번 빼거나, 3으로 한 번 나누면 1로 만들 수 있으므로 `dp[3]`은 1이다.

🔹 dp[3]

• 3을 1로 만드는 방법:
  • 3 → 2 (1을 빼기) → `dp[2] + 1` = 1 + 1 = 2
  • 3 → 1 (3으로 나누기) → `dp[1] + 1` = 0 + 1 = 1
• 더 작은 건 1 → `dp[3]` = 1

i	0	1	2	3	4	5	6	7	8
dp[i]	0	1	1	1	2	3	2	3	3

 

핵심은 할 수 있는 모든 연산을 해본 뒤, 현재 `i`에서의 제일 작은 연산 횟수로 최소 연산 횟수를 갱신해준다는 것이다.

 

코드

import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        // i % 3 == 0 이면 / 3
        // i % 2 == 0 이면 / 2
        // - 1
        // dp[i]는 i일 때, 1로 만들기 위한 최소 연산 횟수
        int[] dp = new int[n + 1];
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }
        }

        System.out.println(dp[n]);
    }
}