[백준] 12852번 : 1로 만들기 2

문제

 

 

접근 방식

기존 1로 만들기 문제에 1이 되는 순서까지 출력하는게 추가된 문제기에

기존 DP 테이블 외에도 순서를 기록할 배열을 더 만들어서 기록해주면 된다.

 

풀이

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());

		int[] dp = new int[n + 1];
		int[] history = new int[n + 1];

		for (int i = 2; i <= n; i++) {
			dp[i] = dp[i - 1] + 1;
			history[i] = i - 1;

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

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

		StringBuilder sb = new StringBuilder();

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

		int num = n;

		while (true) {
			sb.append(num).append(" ");
			if (num == 1) break;
			num = history[num];
		}

		System.out.println(sb);
	}
}