[BOJ] 12852번 1로 만들기 2

문제

1로 만들기 2

코드

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;

	cin >> n;

	int arr[n + 1];
	int arr2[n + 1];
    
	for (int i = 0; i <= n; i++)
	{
		arr[i] = 0;
		arr2[i] = 0;
	}
	
	for (int i = 2; i <= n; i++)
	{
		arr[i] = arr[i - 1] + 1;
		arr2[i] = i - 1;

		if (i % 3 == 0)
		{
			if (arr[i] > arr[i / 3] + 1)
			{
				arr[i] = arr[i / 3] + 1;
				arr2[i] = i / 3;
			}
		}
		if (i % 2 == 0)
		{
			if (arr[i] > arr[i / 2] + 1)
			{
				arr[i] = arr[i / 2] + 1;
				arr2[i] = i / 2;
			}
		}
	}
	cout << arr[n] << '\n';
	cout << n << ' ';
	while (arr2[n])
	{
		cout << arr2[n] << ' ';
		n = arr2[n];
	}
    return (0);
}