백준 소스코드 [C++] 12852 1로 만들기 2

www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

백준 소스코드 [C++] 12852 1로 만들기 2

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int DP[1000001];
int trace[1000001];
void dp(int n) {
	DP[1] = 0;
	trace[1] = 0;
	for (int i = 2; i <= n; i++) {
		DP[i] = DP[i - 1] + 1;
		trace[i]= i-1;
		if (i % 2 == 0 && DP[i] > DP[i / 2] + 1) {
			DP[i] = DP[i / 2] + 1;
			trace[i] = i /2;
		}
		if (i % 3 == 0 && DP[i] > DP[i / 3] + 1) {
			DP[i] = DP[i / 3] + 1;
			trace[i] = i/3;
		}
	}
	cout<<DP[n]<<'\n';
	while (n != 0) {
		cout << n << ' ';
		n = trace[n];
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	dp(n);
	return 0;
}