Baekjoon Online Judge

algorithm practice

-問題を逐次解く

27.動的計画法と最短距離逆追跡

1.作成は1 2

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

public class Main {  
	static int N;
	static int[] dp;
	static final int INF = 1000000000;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   
		StringBuilder sb = new StringBuilder();
        
		N = Integer.parseInt(br.readLine()); 
		dp = new int[N + 1];
        
		Arrays.fill(dp, INF);
		dp[N] = 0;
        
		for(int i = N; i >= 1; i--){
			// 현재 i위치에서 가는 최솟값
			int minValue = dp[i] + 1;

			if(i % 3 == 0) dp[i / 3] = Math.min(dp[i / 3], minValue);
			if(i % 2 == 0) dp[i / 2] = Math.min(dp[i / 2], minValue);
            
			dp[i - 1] = Math.min(dp[i - 1], minValue);
		}        

		sb.append(dp[1] + "\n");
        
		int minValue = dp[1];
		Stack<Integer> stack = new Stack<>();

		for(int i = 1; i <= N; i++){
			if(minValue == dp[i]){
				stack.push(i);
				
				if(i*3 <= N && dp[i * 3] == minValue - 1) i = i*3 - 1;
				else if(i*2 <= N && dp[i * 2] == minValue - 1) i = i*2 - 1;
				
				minValue--;
			}
		}
        
		while(!stack.isEmpty()) {
			sb.append(stack.pop() + " ");
		}
        
		bw.write(sb.toString());
        
		bw.flush();
		br.close();
		bw.close();
	}	
}

import sys

N = int(sys.stdin.readline())
dp = [[0, []] for _ in range(N + 1)] #[최솟값, 경로 리스트]
dp[1][0] = 0 
dp[1][1] = [1]

for i in range(2, N + 1):
	
    #f(x-1) + 1   
    dp[i][0] = dp[i-1][0] + 1
    dp[i][1] = dp[i-1][1] + [i]
    
    #f(x//3) + 1   
    if i % 3 == 0 and dp[i//3][0] + 1 < dp[i][0]:
        dp[i][0] = dp[i//3][0] + 1
        dp[i][1] = dp[i//3][1] + [i]

	#f(x//2) + 1   
    if i % 2 == 0 and dp[i//2][0] + 1 < dp[i][0]:
        dp[i][0] = dp[i//2][0] + 1
        dp[i][1] = dp[i//2][1] + [i]
        
print(dp[N][0])
for i in dp[N][1][::-1]: # 역순 출력
    print(i, end=' ')