[백준] 12852. 1로 만들기 2 (Java)

 

문제

12852번: 1로 만들기 2

 

알고리즘

다이나믹 프로그래밍(DP)

 

 

풀이

1463. 1로 만들기 문제에서 최소로 만드는 과정을 출력하는 조건이 추가된 문제이다.

따라서 동일하게 다이나믹 프로그래밍으로 최솟값을 갱신하면서

갱신할 때의 값을 다른 배열에 따로 저장하고 연산이 끝난 후 역추적하면 된다.

 

 

코드

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());
		int[] dp = new int[N + 1];
		int[] before = new int[N + 1];
		dp[1] = 0;

		for (int i = 2; i <= N; i++) {

			dp[i] = dp[i - 1] + 1;
			before[i] = i - 1;

			if (i % 2 == 0 && dp[i / 2] + 1 < dp[i]) {
				dp[i] = dp[i / 2] + 1;
				before[i] = i / 2;
			}

			if (i % 3 == 0 && dp[i / 3] + 1 < dp[i]) {
				dp[i] = dp[i / 3] + 1;
				before[i] = i / 3;
			}
		}

		sb.append(dp[N]).append("\n");

		int index = N;
		for (int i = 0; i < dp[N] + 1; i++) {
			sb.append(index).append(" ");
			index = before[index];
		}

		System.out.println(sb);
	}
}