[백준 12852: JAVA] 1로 만들기 2 / 동적 프로그래밍 + 역추적

개요

 

dp를 이용해서 구하며,

dp[i] = k → i까지 가는데 걸리는 최소 비용 = k로 배열을 선언하고 풀이하였다.

 

따라서 점화식은 dp[i] = min(dp[i * 3], dp[i * 2], dp[i + 1]) + 1 이 된다.

 

문제

 

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

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

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

 

입력

 

풀이

 

1. dp[n] ~ dp[1]까지를 구한다.

 

2. dp값을 기준으로 (* 2, * 3, +1 이 가능한지) 와 (dp값의 차이가 1인지) 를 확인하며 후보들을 스택에 push한다.

 

3. stack에서 pop하며 출력한다.

 

코드

 

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

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    // 무한대의 값
    private static final int INF = 1_000_000;
    static StringBuilder sb = new StringBuilder();

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

        Arrays.fill(dp, INF);
        //n을 만들기 위해 걸리는 최소 시간 = 0
        dp[n] = 0;

        for(int i = n; i >= 1; i--){
           // 현재 i위치에서 가는 최솟값
           int minValue = dp[i] + 1;

           if(i % 3 == 0) dp[i / 3] = Math.min(dp[i / 3], minValue);
           if(i % 2 == 0) dp[i / 2] = Math.min(dp[i / 2], minValue);
           dp[i - 1] = Math.min(dp[i - 1], minValue);


        }
        // 1까지 가는 최소 횟수
        sb.append(dp[1] + "\n");

        int minValue = dp[1];
        Stack<Integer> stack = new Stack<>();

        for(int i = 1; i <= n; i++){
            if(minValue == dp[i]){
                stack.push(i);

                // 3배의 수의 dp값이 dp[i] - 1과 같은 경우
                if(i * 3 <= n && dp[i * 3] == minValue - 1)
                    // i값은 3배인 수로 변경
                    i = i * 3 - 1;
                // 2배의 수의 dp값이 dp[i] - 1과 같은 경우
                else if(i * 2 <= n && dp[i * 2] == minValue - 1){
                    i = i * 2 - 1;
                }else if(i + 1 <= n && dp[i + 1] == minValue - 1){

                }

                minValue--;
            }
        }

        // 역추적한 결과 출력
        while (!stack.isEmpty()){
            sb.append(stack.pop() + " ");
        }
        bw.write(sb.toString());

        bw.close();
        br.close();
    }
}