0x10 - DP : BOJ12852 1로 만들기2

1463번 1로만들기와 동일한데, 중간경로를 출력하는 부분이 추가된 문제이다

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // 1. 테이블 설정
        // b[i] : i가 1이 되기위한 연산의 최솟값
        // q[i] : 경로를 출력하기 위해 저장하는 값,
        int[] b = new int[n+5];
        int[] q = new int[n+5];

        //2. 초기값설정
        b[1]=0; b[2]=1; b[3]=1;
        q[1]=1; q[2]=1; q[3]=1;

        //3. 점화식
        for (int i = 4; i <= n; i++) {
            b[i] = b[i - 1] + 1;
            q[i] = i - 1;
            if (i % 3 == 0) {
                if (b[i / 3]+1 < b[i]) {
                    b[i] = b[i / 3]+1;
                    q[i] = i / 3;
                }
            }
            if (i % 2 == 0) {
                if (b[i / 2]+1 < b[i]) {
                    b[i] = b[i / 2]+1;
                    q[i] = i / 2;
                }
            }
        }
        System.out.println(b[n]);
        int i=n;
        System.out.print(n+" ");
        while(i!=1) {
            System.out.print(q[i]+" ");
            i=q[i];
        }
    }
}

1. 테이블
   b[i] : i가 1이 되기위한 연산의 최솟값
   q[i] : 경로를 출력하기 위해 저장하는 배열

2. 초기값 설정

3. 점화식
   b[i] = b[i - 1] + 1 하고
   3, 2로 나누어 떨어지는 경우, i/3, i/2와 값 비교하여 최솟값 삽입
   동시에 q값도 채워넣음

4. 출력
   LinkedList처럼 배열에 저장된 값 타고가며 출력