[12852] 1로 만들기 2

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		int[] dp = new int[n + 1];
		int[] arr = new int[n + 1];
		
		Arrays.fill(dp, Integer.MAX_VALUE);
		
		dp[0] = 0;
		dp[1] = 0;
		for(int i=2; i<=n; i++) {
			if(i%3 == 0) {
				if(dp[i/3] + 1 < dp[i]) {
					dp[i] = dp[i/3] + 1;
					arr[i] = i/3;
				}
			}
			if(i%2 == 0) {
				if(dp[i/2] + 1 < dp[i]) {
					dp[i] = dp[i/2] + 1;
					arr[i] = i/2;
				}
			}
			if(dp[i - 1] + 1 <dp[i]) {
				dp[i] = dp[i - 1] + 1;
				arr[i] = i - 1;
			}
		}
		
		System.out.println(dp[n]);
		
		printPath(arr, n);
	}
	
	public static void printPath(int[] arr, int n) {
		if(n==1) {
			System.out.println(n);
			return;
		}

		System.out.print(n + " ");
		printPath(arr, arr[n]);
	}
}