백준 - 1463번: 1로 만들기 (C++)

Pixabay로부터 입수된 JL G님의 이미지 입니다.

 

---

 

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 이번 문제는 숫자가 하나 주어질 때, 이 숫자를 1로 만드는데 필요한 횟수 중, 가장 작은 값을 구하는 문제이다. 숫자에 이용할 수 있는 연산은 아래의 3가지이다.

• 숫자가 3으로 나누어 떨어지면 3으로 나눈다.
• 숫자가 2로 나누어 떨어지면 2로 나눈다.
• 숫자에서 1을 뺀다.

이 문제는 각 숫자마다 도달할 수 있는 최소한의 횟수를 저장하면서 진행하면 답을 구할 수 있는, 전형적은 다이나믹 프로그래밍 문제라 할 수 있다. 예를 들어, 현재 숫자가 12이고 각 숫자마다의 최소 횟수를 저장하는 배열 이름을 dp라고 하자. 가장 처음으로, dp[12]을 아주 큰 값으로 설정한다. 그리고  12는 3으로 나누어 떨어지기 때문에 dp[12]는 dp[12]와 dp[4] + 1(12에서 3으로 나누는 연산을 한 번 해야하기 때문)의 값 중 최소값으로 설정한다. 그리고 12는 2로도 나누어 떨어지기에 dp[12]는 dp[12]와 dp[6] + 1 중 더 작은 값이 될 것이다. 마지막으로 dp[12]는 dp[12]와 dp[11] + 1 중 더 작은 값이 될 것이다. 

 

#include <iostream>
#define MAX 1000001

using namespace std;

int X;
int dp[MAX];

int Check(int num)
{
    if (num == 1)
        return 0;

    if (dp[num] > 0)
        return dp[num];

    int result = MAX + MAX;

    if (num % 3 == 0)
        result = min(result, Check(num / 3) + 1);

    if (num % 2 == 0)
        result = min(result, Check(num / 2) + 1);
    
    result = min(result, Check(num - 1) + 1);

    return dp[num] = result;
}

int main()
{
    ios_base::sync_with_stdio(0);
	std::cout.tie(NULL);    
	std::cin.tie(NULL);

    for (int i = 0; i < MAX; ++i)
        dp[i] = -1;

    cin >> X;

    int answer = Check(X);    

    cout << answer << endl;

    return 0;
}