[백준] 1로 만들기2 12852번 C++ 풀이

https://www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

#include <iostream>
#include <algorithm>
using namespace std;
int N;
int dp[1000001];
int before[1000001];
int main(void)
{
	cin >> N;

	dp[1] = 0; //1을 만들기위해선 아무 연산을 안해도 됨.
	before[1] = 0;
	for ( int i = 2; i <=N ; i++ )
	{

		dp[i] = dp[i - 1]+1; // 1을 더하는게 최대 연산 횟수를 가질것.
		before[i] = i - 1;

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

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

	}

	cout << dp[N]<<"\n";
	while (N != 0) // N에서 0이 될때까지 전의 수를 찾음.
	{
		cout << N << " ";
		N = before[N];
	}

}

before[i] 는 i를 만들기위해 전에 숫자가 뭐였는지를 담는 배열입니다.

dp[i]는 i번째가 1을 만들기위해 최소로 해야하는 연산을 담습니다.