백준 12852번 : 1로 만들기 2 풀이 (Java)

www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

6의 배수를 조심하자

Solution

1. 이 문제는 다이나믹 프로그래밍, DP 로 풀어야 하는 문제이다. 최대 인풋이 10의 6승이고, 그렇기에 최대 O(n) 으로 풀어야 할 것이다.

2. N 을 1로 만드는 것이라서 top-down 방식으로 풀까 하다가 웬지 어려울 것 같아서 bottom-up 으로 풀었는데, 출력을 위해서 반복문을 한번 더 돌려야했다. 푼 뒤에 top-down 을 시도해봤는데 이 편이 더 어려운 것 같다..

3. N+1 크기의 dp 배열을 만들고, dp[i] 에는 i 를 1로 만드는 데 필요한 연산 횟수를 담는다. dp[1] = 0, dp[2] = 1 일 것이다.

4. 이제, 우리가 할 수 있는 세 가지 연산을 했을 때의 횟수 를 구해줘야 하는데, 이는 

 1을 빼주는 경우 : 1을 빼주는 연산 횟수 ( 1 ) + (i - 1) 을 1로 만드는 데 필요한 연산 횟수( dp[i-1] )

 2로 나눠주는 경우 : 2로 나눠주는 연산 횟수 ( 1 ) + (i / 2) 를 1로 만드는 데 필요한 연산 횟수 (dp[i / 2])

 3으로 나눠주는 경우 : 3으로 나눠주는 연산 횟수 ( 1 ) + (i / 3) 를 1로 만드는 데 필요한 연산 횟수 (dp[i / 3])

 

이다. 이 셋을 비교해주면서 최소인 것들을 담아주면서 dp 배열을 완성시켜준다. 이후, N 이 1이 될 때까지 다시 같은 연산을 해주면서 최소의 경우들을 찾고, 해당하는 수들을 bufferedWriter 에 써주면 그 동안의 기록들이 완성된다.

 

Source Code

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

public class Main {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

    static void solve() throws IOException{
        int N = Integer.parseInt(bufferedReader.readLine());
        if(N == 1) {
            System.out.println(0);
            System.out.println(1);
            return;
        }
        int[] dp = new int[N+1];
        dp[N] = 0;
        dp[1] = 0;
        dp[2] = 1;
        int i = 3;
        while(i <= N) {
            int minusOneResult = dp[i-1] + 1;
            int divByThreeResult = Math.min(minusOneResult, dp[i/3] + 1);
            int divByTwoResult = Math.min(minusOneResult, dp[i/2] + 1);
            if(i % 3 == 0) {
                if(i % 2 == 0) {
                    dp[i] = Math.min(divByThreeResult,divByTwoResult );
                }
                else {
                    dp[i] = divByThreeResult;
                }
            }
            else if(i % 2 == 0) {
                dp[i] = divByTwoResult;
            } else {
                dp[i] = minusOneResult;
            }
            i++;
        }
        int n = N;
        bufferedWriter.write(dp[N] + "\n");
        bufferedWriter.write(N + " ");
        while(n > 1) {
            if(n % 3 == 0 && dp[n / 3] + 1 < dp[n-1] + 1) {
                n /= 3;
                bufferedWriter.write(n + " ");
            } else if(n % 2 == 0 && dp[n / 2] + 1 < dp[n-1] + 1) {
                n /= 2;
                bufferedWriter.write(n + " ");
            } else {
               n -= 1;
               bufferedWriter.write(n + " ");
            }
        }


    }

    public static void main(String[] args) throws IOException {
        solve();
        bufferedWriter.close();
        bufferedReader.close();
    }
}