백준 12852번 _ 1로 만들기 2

2020-06-13 · 배운 것 · 2분 읽기

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

12852번: 1로 만들기 2

풀이방법

1. 연산을 사용하는 횟수의 최솟값을 찾고
2. 1에서 이용한 dp값을 역추적해서 경로를 찾는다.

코드

#include <iostream>
#include <algorithm>

#define MAXN 1000000
#define INF 987654321

using namespace std;

int dp[MAXN + 1];
int N;

void dpInit()
{
	for (int i = 1; i <= N; i++)
		dp[i] = -1;
}

int GetMinValue(int n)
{
	int& ret = dp[n];
	if (ret != -1)
		return ret;

	if (n == 1)
		return ret = 0;

	ret = INF;

	if (n % 3 == 0)
		ret = min(ret, GetMinValue(n / 3)+1);

	if (n % 2 == 0)
		ret = min(ret, GetMinValue(n / 2)+1);

	ret = min(ret, GetMinValue(n - 1)+1);

	return ret;
}

void print(int n)
{
	if (n == 0)
		return;

	cout << n <<' ';

	if (n % 3 == 0 && (dp[n] == dp[n / 3] + 1))
		print(n / 3);

	else if (n % 2 == 0 && (dp[n] == dp[n / 2] + 1))
		print(n / 2);

	else if (n -1 >= 0 && (dp[n] == dp[n - 1] + 1))
		print(n - 1);

}

int main()
{
	cin >> N;
	dpInit();
	cout << GetMinValue(N) << endl;
	print(N);

	return 0;
}