백준 1463번 1로 만들기

문제 링크입니다: 

동적 계획법을 이용하여 재귀와 비재귀 함수를 작성해봤습니다.

해당 문제처럼 하나의 숫자만 입력받는다면 비재귀 함수가 빠르겠지만 반복문 안에서 여러개의 숫자가 1로 만드는데 걸리는 횟수를 구한다면 재귀함수가 더 유용할 것이라고 생각합니다.

/*

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

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

연산 횟수를 최소화하여 X를 1로 만드시오

*/

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

 

int cache[1000001]; //최대 1000000

 

int minish(int X)

{

        int &result = cache[X];

        if (result != -1)

               return result;

 

        if (X == 1)

               return result;

 

        //최소 연산횟수를 구한다

        int cnt = numeric_limits<int>::max();

        if (!(X % 3))

               cnt = min(cnt, minish(X / 3));

        if (!(X % 2))

               cnt = min(cnt, minish(X / 2));

        cnt = min(cnt, minish(X - 1));

 

        return result = cnt + 1; //추가연산했으니 + 1

}

 

/*

int minish(int X)

{

        cache[1] = 0;

        for (int i = 2; i <= X; i++)

        {

               cache[i] = cache[i - 1] + 1; //1을 빼거나

               if (!(i % 2)) //1을 뺐을 경우 연산횟수 vs 2로 나누었을 경우 연산 횟수

                       cache[i] = min(cache[i], cache[i / 2] + 1);

               if (!(i % 3)) //1을 뺐을 경우 연산횟수 vs 3으로 나누었을 경우 연산 횟수

                       cache[i] = min(cache[i], cache[i / 3] + 1);

        }

        return cache[X];

}

*/

 

int main(void)

{

        int X;

        cin >> X;

        if (X > 1000000)

               exit(-1);

        memset(cache, -1, sizeof(cache));

        cache[0] = cache[1] = 0;

        cout << minish(X) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~