백준 12852 c++ : DP

#include <iostream>
#include <vector>

using namespace std;

void find_answer(int N) {
	cout << "find_answer()\n";

	int count = 0;
	vector<int> DP(N + 1, 0);
	vector<int> next(N + 1, 0);
	int i, j;

	//횟수의 최솟값, 최솟값으로 가기까지 거쳐가는 정수

	for (i = 2; i <= N; i++) {
		DP[i] = DP[i - 1] + 1;//1씩 더하는 경우
		if (i % 3 == 0) {
			DP[i] = min(DP[i], DP[i / 3] + 1);
		}
		if (i % 2 == 0) {
			DP[i] = min(DP[i], DP[i / 2] + 1);
		}

		for (j = 0; j <= N; j++) {
			cout << DP[j] << " ";
		}
		cout << "\n";
	}

	cout << DP[N] << "\n";
	cout << N << " ";
	while (N > 1) {
		if (N % 3 == 0 && DP[N / 3] == DP[N] - 1) {
			cout << N / 3 << " ";
			N = N / 3;
		}
		else if (N % 2 == 0 && DP[N / 2] == DP[N] - 1) {
			cout << N / 2 << " ";
			N = N / 2;
		}
		else {
			cout << N - 1 << " ";
			N--;
		}
	}

	return;
}

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

	int N;
	
	cin >> N;
	find_answer(N);

	return 0;
}