[C/C++] 백준 1463번 - 1로 만들기

 

<코드>

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1000001];

int solve(int N)
{
	dp[1] = 0;
	for (int i = 2; i <= N; i++)
	{
		// 3번 연산
		dp[i] = dp[i - 1] + 1;

		// 1번 연산
		if (i % 3 == 0)
		{
			if (dp[i] > dp[i / 3] + 1)
				dp[i] = dp[i / 3] + 1;
		}

		// 2번 연산
		if (i % 2 == 0)
		{
			if (dp[i] > dp[i / 2] + 1)
				dp[i] = dp[i / 2] + 1;
		}
	}

	return dp[N];
}

int main(void)
{
	int  X;
	cin >> X;

	cout << solve(X) << '\n';

	for (int i = 1; i <= X; i++)
	{
		//cout << i << " : " << dp[i] << '\n';
	}

	return 0;
}

 

 

www.acmicpc.net/problem/1463

1463번: 1로 만들기