1로 만들기

문제

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

X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

출력

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

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

해결

D[i]는 i에서 1로 만드는 최소 연산 횟수다.

• 1을 빼는 연산은 언제나 가능하므로 D[i-1]+1을 먼저 후보로 둔다.
• i가 2로 나누어떨어지면 D[i/2]+1을 비교한다.
• i가 3으로 나누어떨어지면 D[i/3]+1도 비교한다.

허용되지 않는 나눗셈 후보를 점화식에 넣으면 안 된다. 특히 6처럼 두 나눗셈이 모두 가능한 수도 있으므로 가능한 후보의 최솟값을 각각 비교한다.

작은 수의 답부터 채우기

D[i]를 i에서 1까지 필요한 최소 연산 횟수라고 두자. 마지막에 어떤 연산을 할지 생각하면 i−1, i/2, i/3 중 허용되는 다음 상태의 정답을 이미 알고 있어야 한다. 모두 i보다 작으므로 D[1]=0에서 시작해 i를 2부터 N까지 늘리면 된다.

예를 들어 10에서는 먼저 1을 빼는 경로의 비용 D[9]+1을 후보로 둔다. 10은 2로 나누어지므로 D[5]+1도 비교한다. 3으로는 나누어지지 않는다. D[9]=2이므로 10→9→3→1의 3회가 답이다. i=6처럼 2와 3 양쪽으로 나누어지는 수는 두 후보를 모두 비교해야 하므로 두 조건을 else if로 묶으면 안 된다.

기존 코드의 table[n / 2]와 table[n / 3]는 반복 중인 i가 아니라 최종 입력 n을 참조했다. 이 오류는 작은 예제에서 우연히 가려질 수 있어, 점화식의 인덱스와 구현의 인덱스를 함께 확인해야 한다. N=1이면 반복하지 않고 0을 출력한다. O(N) 시간과 O(N) 배열 공간이 필요하다.

i	가장 좋은 첫 연산	D[i]
1	이미 1	0
2	2로 나누기	1
3	3으로 나누기	1
4	2로 나누기	2
6	3으로 나누기	2
9	3으로 나누기	2
10	1 빼서 9로 이동	3

6은 6→3→1과 6→2→1이 모두 2회다. 표의 “가장 좋은 첫 연산”이 유일한 선택을 뜻하지는 않는다. DP는 경로 자체가 아니라 최소 횟수만 저장하므로 동률을 구별하지 않아도 된다.

소스코드

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

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

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }
        System.out.println(dp[n]);
    }
}

백준 원문 문제