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

문제

https://www.acmicpc.net/problem/12852

 

풀이

1로 만들기 풀이와 유사하지만, x에서 1까지 어떤 숫자를 선택했는지를 저장해야 한다.

next[x]는 x 다음 ( /3, /2, -1) 연산을 통해 어떤 숫자가 되어야 최소 작업으로 1이 될 수 있는 지를 저장한다.

 

package boj.dp;

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

public class Boj_12852_1로만들기2 {
	static int[] d;
	static int[] next;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int x = Integer.parseInt(br.readLine());
		d = new int[x+1];
		d[1] = 0;
		next = new int[x+1];

		int min = dp(x); // 답 도출
        
		StringBuilder sb = new StringBuilder();
		sb.append(min).append("\n");
		int nextNum = x;
		while(nextNum >= 1) {
			sb.append(nextNum).append(' ');
			nextNum = next[nextNum];
		}
        
		System.out.println(sb);
		br.close();
	}
	
	public static int dp(int x) {
		if(d[x] > 0 || x<=1) {
			return d[x];
		}
		
		int min = Integer.MAX_VALUE;
		if(x%3 == 0) {
			if(min > dp(x/3)+1) {
				min = d[x/3]+1;
				next[x] = x/3;
			}
		}
		if(x%2 == 0) {
			if(min > dp(x/2)+1) {
				min = d[x/2]+1;
				next[x] = x/2;
			}
		}
		if(min > dp(x-1)+1) {
			min = d[x-1]+1;
			next[x] = x-1;
		}
		
		return d[x] = min;
	} 
}