[BOJ] 12852 - 1로 만들기 2

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

난이도: 실버 1

사용언어: JAVA

 

풀이

기본적인 문제의 풀이는 아래의 문제와 같습니다.

 

jooona.tistory.com/104

[BOJ] 1463 - 1로 만들기

단지 마지막에 1로 만든 경로를 출력해주기만 하면 됩니다. 그냥 배열을 하나 더 만들어서 경로를 추적해주기만 하면 됩니다.

 

import java.io.*;
import java.util.Arrays;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int i;
        int[] arr = new int[N + 1]; // 다이나믹 프로그래밍을 위한 배열
        int[] log = new int[N + 1]; // 경로 추적을 위한 배열
        Arrays.fill(arr, Integer.MAX_VALUE);
        arr[0] = 0;
        arr[1] = 0;
        for (i = 2; i <= N; i++) {
            if (i % 3 == 0) { // 3으로 나누어 떨어지면
                arr[i] = arr[i / 3] + 1; // 저장
                log[i] = i / 3;
            }
            if (i % 2 == 0) {
                if (arr[i] > arr[i / 2] + 1) { // 2로 나누어 떨어지면서 연산 횟수가 3으로 나눌 때 보다 작다면
                    arr[i] = arr[i / 2] + 1;
                    log[i] = i / 2;
                }
            }
            if (arr[i] > arr[i - 1] + 1) { // 1을 뺐을 때의 연산 횟수가 2나 3으로 나눌 때 보다 작다면
                arr[i] = arr[i - 1] + 1;
                log[i] = i - 1;
            }
 
        }
        bw.write(String.valueOf(arr[N]) + "\n"); // 최소 연산 횟수 출력
        i = N;
        bw.write(String.valueOf(N) + " ");
        while (i > 1) {
            bw.write(String.valueOf(log[i]) + " ");
            i = log[i];
       } // 경로 추적
        bw.flush();
        bw.close();
        br.close();
    }
}