[백준(Baekjoon)][자바(java)] 12852 : 1로 만들기 2 / 동적 계획법과 최단거리 역추적

 

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

12852번: 1로 만들기 2

 

( 1463번 : 1로 만들기 )

문제  :  https://www.acmicpc.net/problem/1463
풀이  :  https://hyunjiishailey.tistory.com/124

 

문제 풀이

 

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

public class Main {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		br.close();

		int dp[][] = new int[n + 1][2], 	// cnt, num
			c[] = new int[3], 				// calculate
			num_cur, num, num_min = -1, cnt_min, i;
		dp[0][0] = n;
		for (num_cur = 2; num_cur <= n; num_cur++) {
			c[0] = num_cur - 1;
			c[1] = num_cur % 2 == 0 ? num_cur / 2 : 0;
			c[2] = num_cur % 3 == 0 ? num_cur / 3 : 0;
			cnt_min = n;
			for (i = 0; i < 3; ++i) {
				num = c[i];
				if (cnt_min > dp[num][0]) {
					cnt_min = dp[num][0];
					num_min = num;
				}
			}
			dp[num_cur][0] = cnt_min + 1;
			dp[num_cur][1] = num_min;
		}

		num = n;
		StringBuilder sb = new StringBuilder();
		sb.append(dp[num][0] + "\n");
		while (num > 0) {
			sb.append(num + " ");
			num = dp[num][1];
		}
		System.out.println(sb.toString());

	}
}

 

-  정수 x ( 1 < x <= n ) 에서 1을 만들 수 있는 최소 연산 횟수, 다음 숫자를 담을 dp[n+1][2] 배열, 
   정수 x에서 3가지 연산을 각각 수행한 결과 값을 저장할 c[3] 배열 생성

-  정수 num_cur( 2 ~ n  ☞  bottom-up ) 에서 수행한 3개의 연산( c[i] ( 0 <= i < 3 ) ) 중
   1로 만들 수 있는 연산 횟수( dp[c[i][0]] )의 최솟값( cnt_min )과 그 수( num_min = dp[c[i][1]] )를 구함

-  정수 num( = n )에 대해 최종적으로 구한 최소 연산 횟수( dp[num][0] )와 함께
   num 부터 시작해서 dp[num][1] 에 담긴 다음 수를 추적하며 StringBuilder에 담아 한꺼번에 출력