백준 알고리즘
[백준 알고리즘] 1463번 1로 만들기
ChocoPeanut
2017. 5. 22. 22:37
1로 만들기
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오.
#include<iostream>
using namespace std;
int dp[1000001];
int make_one(int num)
{
if (num == 1)
{
return 0;
}
if (dp[num] > 0)
{
return dp[num];
}
dp[num] = make_one(num - 1) + 1;
if (num % 3 == 0)
{
int k = make_one(num/3) + 1;
if (dp[num] > k)
{
dp[num] = k;
}
}
if (num % 2 == 0)
{
int k = make_one(num/2) + 1;
if (dp[num] > k)
{
dp[num] = k;
}
}
return dp[num];
}
int main()
{
int num;
cin >> num;
cout << make_one(num) << endl;
}