[백준 알고리즘] 1463번 1로 만들기

1로 만들기

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 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;

}