백준

[1463] 1로 만들기

Jcoder 2018. 8. 3. 21:07


#include <iostream>
#define MAX 1000001
using namespace std;
int min(int a, int b);
int dp[MAX];
int main()
{
int testcase, i;
cin >> testcase;
dp[0] = dp[1] = 0;
for (i = 2; i <= testcase; i++)
{
dp[i] = dp[i - 1] + 1;
if (i % 2 == 0)
dp[i] = min(dp[i], dp[i / 2] + 1);
if (i % 3 == 0)
dp[i] = min(dp[i], dp[i / 3] + 1);
}
cout << dp[testcase] << endl;
return 0;
}
int min(int a, int b)
{
return (a < b) ? a : b;
}