1463 - 1로 만들기

문제: boj.kr/1463
날짜: 08/29 (목)
성공여부: O (00:37:07)

 

실버3의 DP 문제이다.

 

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

 

정수 x에 대해서 적용할 수 있는 3가지 연산인데, 뭔가 연산의 순서가 있는 것처럼 보여서 순서를 지켜서 풀려고 하면 틀린다. 위의 3가지 연산은 3가지 경우의 수이고 정수 x에 대해서 각각 모두 적용시켜서 모든 경우의 수를 찾아서 푸는 문제이다. 라는 생각을 가지고 완탐으로 풀 수 있을까? 라고 생각해보아야 한다. 그럼 시간 복잡도는 100만개의 숫자에 대해서 3개의 연산을 하므로 3^100임을 알 수 있다.

 

근데 문제에서 주어진 시간이 0.15초이므로 무조건 시간 초과가 날 것이다.. 그럼 어떻게 풀어야할까? 결론은 DP이다. 왜냐면 3으로 나누든 2로 나누든 1을 빼든 중복되는 숫자가 발생을 한다.

 

12 -> 4 -> 2 -> 1

12 -> 6 -> 2 -> 1

 

간단한 예제이긴 한데, 12를 1로 만드는 2가지 방법을 보면 중간에 2가 중복되는 것을 볼 수 있다. 이는 DP의 중복 부분 문제 조건에 부합하며 DP 자체가 완탐을 하는 것에 메모이제이션 기술을 이용한 기법이므로 이를 활용해 시간 복잡도를 다시 계산해보자.

 

일단 아는 문제에 대해서는 O(1)이다.

그리고 해당 문제는 1이 되는 최소 연산횟수를 구하는건데 만약 입력이 1이면 연산을 안해도 되므로 0이 답이된다. 그럼 우린 dp[1] = 0; 이라는 답을 이미 가지고 있으니 이를 시작으로 2부터 n까지의 답을 구하기만 하면 된다. 왜냐면 1,2,3 연산이 모두 1~n 범위 내 숫자로만 이루어지기 때문에 2부터 n까지 차례대로 메모이제이션을 이용해 O(1)로 접근하여 답을 구하면 된다. 그럼 총 O(N)이라는 시간 복잡도를 가진다. 즉, 100만에 해결이 가능해졌다.

 

코드

import java.io.*;

public class Main {
    // 시간제한 0.15초, 메모리제한 128MB
    static int[] dp;
    static int n;

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

        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            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);

            dp[i] = Math.min(dp[i], dp[i-1] + 1);
        }

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