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;
}
'백준 알고리즘' 카테고리의 다른 글
[백준 알고리즘] 2579번 계단 오르기 (0) | 2017.05.27 |
---|---|
[백준 알고리즘] 1149번 RGB거리 (0) | 2017.05.23 |
[백준 알고리즘] 10817번 세 수 (0) | 2017.05.20 |
[백준 알고리즘] 10164번 격자상의 경로 (0) | 2017.05.20 |
[백준 알고리즘] 9461번 파도반 수열 (0) | 2017.05.20 |