[백준 BoJ] 12582 - 1로 만들기 2

// https://www.acmicpc.net/problem/12852
// 1로 만들기 2
#include<iostream>
#include<algorithm>

using namespace std;
int dp[1000001], path[1000001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int X;

	cin >> X;

	dp[1] = 0;
	path[1] = -1;
	
	for (int i = 2; i <= X; i++) {
		dp[i] = dp[i - 1] + 1;
		path[i] = i - 1;

		if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) {
			dp[i] = dp[i / 2] + 1;
			path[i] = i / 2;
		}

		if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
			dp[i] = dp[i / 3] + 1;
			path[i] = i / 3;
		}
		
	}
	cout << dp[X] <<"\n";

	while (X != -1) {
		cout << X << " ";
		X = path[X];
	}

}