백준 12852번 : 1로 만들기 2

[레벨5]

 

· 문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

· 입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.

 

· 출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.

 

· 풀이

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

public class Main {
	
	static int T;
	static int n, m;

	public static void main(String[] args) throws Exception {
		
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        StringBuilder sb = new StringBuilder();
	        
	        int N = Integer.parseInt(br.readLine());
	        
	        int[] D = new int[N+1];	//회수 저장.
	        int[] S = new int[N+1];	//경로 저장.

	        for (int i = 2; i <= N; i++) {
	            D[i] = D[i-1] + 1;
	            S[i] = i-1;
	            if (i % 2 == 0 && D[i] > D[i/2] + 1) {
	                D[i] = D[i/2] + 1;
	                S[i] = i/2;
	            }
	            if (i % 3 == 0 && D[i] > D[i/3] + 1) {
	                D[i] = D[i/3] + 1;
	                S[i] = i/3;
	            }
	        }

	        System.out.println(D[N]);
	        
	        do {
	            sb.append(N + " ");
	            N = S[N];
	        } while (N != 0);
	        
	        System.out.print(sb);
	}
}