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

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
	int n;

	cin >> n;

	int dp[1000001];

	dp[1] = 0;

	for (int i = 2; i <= n; i++)
	{
		dp[i] = dp[i - 1] + 1; //이전 수 보다 횟수 1 많음 

		if (i % 2 == 0) //그런데 2로 나누어진다면
		{
			dp[i] = min(dp[i], dp[i / 2] + 1); //1많은 이전 수와  2로 나누어 진수보다 한개 많은거랑 비교
		}
		if (i % 3 == 0) //그런데 3으로 또 나누어질수도 있따면
		{
			dp[i] = min(dp[i], dp[i / 3] + 1); //1많은 이전 수와  3로 나누어 진수보다 한개 많은거랑 비교
		}
	}

	cout << dp[n] << endl;

	return 0;
}//end of main