백준 12852 Java

참고

---

1

2 -> 1

3 -> 1

4 -> 2 -> 1

5 -> 4 -> 2 -> 1

6 -> 3 -> 1 ( 6 -> 2 -> 1)

7 -> 6 -> 3 -> 1

8 -> 4 -> 2 -> 1

9 -> 3 -> 1

7과 같이 2와 3으로 나누어 떨어지지 않는 경우 어쩔 수 없이 -1 연산이 필요하므로
6에서 1을 만드는 연산 횟수에 1을 더하면 되겠다.

하지만 9와 같이 2 또는 3으로 나누어 떨어질 경우, 하나 더 작은 수인 8보다 연산 횟수가 적은 경우도 있다.

N에서 1을 만드는 최소 연산 횟수를 구해야하므로, 적절히 분기를 나누어 연산횟수를 비교한 후 최소인 값을 저장해야겠다.

---

Code

package test;

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

public class P12852 {

	public static void main(String[] args) throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		int[] dp = new int[N + 1]; // dp[N] : N을 1로 만다는 최소 연산 횟수
		int[] before = new int[N + 1]; // before[N] : dp[N]을 구할 때 N 다음의 수

		dp[1] = 0;
		before[1] = -1;

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

			if(i % 2 == 0 && dp[i] > dp[i / 2] + 1) {
				dp[i] = dp[i / 2] + 1;
				before[i] = i / 2;
			}
			if(i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
				dp[i] = dp[i / 3] + 1;
				before[i] = i / 3;
			}
		}
		
		int num = dp[N]; // 총 (최소)연산 횟수
		
		bw.write(String.valueOf(num) + '\n');
		
		int point = N;
		
		// N에서 1을 만드는 방법에 포함되어 있는 수
		for(int i = 0; i <= num; i++) { 
			bw.write(String.valueOf(point) + " ");
			point = before[point];
		}
		
		bw.flush();
		bw.close();
		br.close();
	}

}