[백준] 1로 만들기 2 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

12852번: 1로 만들기 2

[문제] 

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

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

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

[입력]

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

[출력]

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

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

 

---

[풀이]

1. 3으로 나누어 떨어지는 경우, 2로 나누어 떨어지는 경우, 1을 뺐을 때에 맞춰 각 계산을 해준다.

2. 각 경우에 이전 횟수 + 1보다 현재 횟수가 적다면 현재 것으로 갱신해준다.

3. 2. 에서 현재 값으로 갱신될 때는 경로 배열에도 값을 담아준다.

4. StringBuilder에 값을 담아준다.

5. 경로의 배열 값에 든 것을 StringBuilder에 담아준다.

6. 결과를 출력한다.

[접근]

1. 위 조건에 맞춰서 계산한 값을 dp 배열에 담아주면 최소 횟수는 구할 수 있다고 생각하였다.

2. 최소 횟수에 맞는 값을 출력을 어떻게 해야 할지 어려웠는데 해당 값에 어디로 이동해야 하는 지를 담아주고 처리하였다.

[코드]

import java.io.*;
import java.util.*;

public class Main {

	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[] dp = new int[n + 1];	// 최소 횟수
		int[] path = new int[n + 1];	// 경로
		
		//초기화
		Arrays.fill(dp, Integer.MAX_VALUE);

		dp[1] = 0;
		
		for (int i = 2; i <= n; i++) {
			// 3으로 나누어 떨어질 때
			if (i % 3 == 0) {
				// 현재 횟수 vs 3 나눴을 때 횟수 + 1
				if(dp[i / 3] + 1 < dp[i]) {
					dp[i] = dp[i / 3] + 1;
					path[i] = i /3;
				}
			}
			// 2로 나누어 떨어질 때
			if (i % 2 == 0) {
				// 현재 횟수 vs 2 나눴을 때 횟수 + 1
				if(dp[i / 2] + 1 < dp[i]) {
					dp[i] = dp[i / 2] + 1;
					path[i] = i / 2;
				}
			}
			// 1을 뺄 때
			if (dp[i - 1] + 1 < dp[i]) {
				dp[i] = dp[i - 1] + 1;
				path[i] = i - 1;
			}
		}

		// 최소 횟수 출력
		sb.append(dp[n] + "\n");

		// 경로 숫자 다 담기
		while (n > 0) {
			sb.append(n + " ");
			n = path[n];
		}

		System.out.println(sb.toString());
	}
}