본문 바로가기
백준 알고리즘

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

by ChocoPeanut 2017. 5. 22.

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;

}