[ 백준 1463 ] 1로 만들기 (C++)

백준의 1로 만들기(1463) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

주어진 숫자를 '1'로 만드는데 연산을 해야하는 최소의 횟수를 구해야 하는 문제이다.

본인은 2가지 방법으로 문제를 접근해 보았다.

첫 번째는 주어진 N을 1로 만들기 위해서 가능한 모든 경우를 다 따져보는 완전탐색이다.

완전탐색 중에서도, 너비우선탐색(BFS)을 이용해서 접근 하였다.

1차원 Visit배열을 선언해서 중복된 탐색을 하지 않도록 구현해 주었다.

두 번째는 Dynamic Programming(DP) 방법으로 접근해보았다.

지금부터는 DP로 푸는 방법에 대해서 구체적으로 알아보자.

먼저, 1차원 배열을 하나 선언해주었다. DP[] 라는 배열인데, 이 배열의 의미는 다음과 같다.

DP[a] = b 의 의미는 "a를 1로 만드는데 취해야 하는 연산의 최소 횟수는 b번 입니다." 이다.

그럼 계산을 하기 전, 초기식을 한번 생각해보자.

DP[0] 의 값은 얼마일까 ? 이를 해석해보면, "0을 1로 만드는데 취해야 하는 연산의 최소 횟수는 몇 번인가요?" 가 된다.

0은 입력값의 범위에 속하는 숫자가 아니기 때문에 '0'으로 설정해 주었다.

그럼 DP[1]의 값은 얼마일까? "1을 1로 만드는데 취해야 하는 연산의 최소횟수는 몇 번인가요 ?"

1은 그 자체로 1이기 때문에, 더 이상의 연산이 필요없다. 즉, DP[1]의 값은 '0'이 된다.

그럼 이 식들을 토대로 더 큰 숫자들의 결과값을 구해보자.

마치, 주어진 N 값을 1로 만드는 것이 아닌, 1부터 N까지 점점 증가하는 방식으로 "상대적으로 더 작은 값을 1로 만드는데 구해야 하는 연산의 최소 횟수들을 통해서 더 큰 숫자들을 구하는 방식" 으로 구해보는 것이다.

문제에서 제시한 방법과 달리, 큰 숫자에서 작은 숫자로 내려 오는 것이 아니라, 작은 숫자에서 큰 숫자로 올라가기 때문에

문제에서 제시한 3가지 연산을 다음과 같이 역으로 생각해줄 필요가 있다.

1) 3으로 나누어 떨어지면 3으로 나눈다. → 3으로 나누어 떨어지면 3을 곱한다.

2) 2로 나누어 떨어지면 2로 나눈다. → 2로 나누어 떨어지면 2를 곱한다.

3) 1을 뺀다 → 1을 더한다.

DP[2]의 값을 생각해보자.

2를 1로 만들 때 걸리는 최소 연산 횟수를 구하기 위해서 1에서 2로 갈 때 취해야 하는 연산의 최소 횟수를 생각해보자.

물론, 주어진 연산 3가지 중에서이다.

우리는 2가지 방법을 선택할 수가 있다. 첫 번째는 '1'에서 + 1 을 통해서 '2'를 만드는 것이다.

이는, 3가지 연산 중에서 3번인, "1을 뺀다" 에 속하는 연산이다. 우리는 반대로 Bottom - Up 방식으로 구현하고 있으므로

+ 1을 통해서 "1을 빼는 연산"을 진행할 수 있다.

또 한가지 연산은 '1'에서 x2를 통해서 '2'를 만드는 것이다.

이는, 3가지 연산 중에서 2번 연산인, "2로 나누어 떨어지면, 2로 나눈다." 에 속하는 연산이다.

위에서 말했듯이, / 2를 하는 과정을, x 2로 생각하고 진행할 수 있다.

그럼, 1에서 2로 갈 때, 우리가 취할 수 있는 연산의 경우의 수는 2가지가 있는데, 이 중, 최소의 연산 횟수는 몇 번일까 ??

바로, "우리가 취했던 2가지 연산 중, 더 최소 횟수를 갖는 연산 횟수"가 최소의 연산횟수가 될 것이다. 당연한 이야기이다.

위에서 얘기해서 알겠지만, DP[2]의 값은 어느 연산을 진행하더라도 '1번만' 진행하면 '1'을 만들 수 있기 때문에 DP[2] = 1

이 된다.

그럼 DP[3]의 값을 구해보자.

마찬가지로, 1에서 3을 만드는 경우를 생각해보자. 딱 생각하는 방법으로는 크게 2가지 방법이 있다.

1에서 + 1, + 1을 통해서 '3'을 만드는 경우와, '1'에서 x3을 통해서 '3'을 만드는 경우가 있다.

먼저, 1에서 + 1, + 1을 통해서 '3'을 만드는 경우를 생각해보자.

1에서 + 1을 하면 '2'가 되고, 우리는 이 '2'라는 숫자에서 한번 더 + 1을 통해서 '3'을 만드는 과정이라고 생각할 수 있다.

그럼, '2'라는 숫자를 만드는데 드는 최소의 연산횟수를 'a번' 이라고 가정해보자.

우리는 이 a번에서, '+1'이라는 연산을 한번 더 진행하기 때문에, 결과적으로 'a + 1'번의 연산을 진행한다는 것을 알 수 있다.

우리는 이 'a번'의 값을 알고 있다. 바로, DP[]라는 배열에 저장을 해 왔기 때문이다. 즉 ! DP[2] + 1을 한 값이, 1 에서 +1, +1을 통해서 '3'을 만드는데 취해야 하는 연산의 횟수가 될 것이다. 이렇게 계산한다면, DP[3] = DP[2] + 1이므로, 1 + 1 = 2가 된다. 실제로, +1을 2번하기 때문에, 이렇게 연산을 한다면 DP[3]의 값은 '2'가 될 것이다.

두 번째 방법은 1에서 x3을 통해서 '3'을 만드는 경우이다. 여기서도 마찬가지로, '1'을 1로 만드는데 취해야 하는 연산의 최소횟수를 'a번' 이라고 가정해보자. 우리는 이 a번에다가 x3 이라는 연산을 한번 더 취하기 때문에, 결과적으로, 'a + 1번' 연산을 진행하게 된다. 우리는 이 a번의 값을 DP라는 배열에 저장해놨기 때문에, 알고 있다. DP[1] = 0 이고, 이렇게 계산한다면

DP[3] = DP[1] + 1이 된다. 즉 ! 1이 되는 것이다. 실제로 '1'에서 'x3'이라는 연산을 한 번만 취하면 '3'을 만들 수가 있다.

이는 역으로, 3에서 1을 만들기 위해서는 / 3을 한번만 진행하면 된다는 것을 의미한다.

그럼 우리에게 DP[3]의 값은 현재 2가지가 있다.

1에서 + 1, + 1을 통해서 구한 DP[3] = 2라는 값과,

1에서 x 3 을 통해서 구한 DP[3] = 1이라는 값이 있다. 이 값 중에 최소값은? 당연히 모든 결과값에서의 최소값을 구하면 되므로, DP[3] = 1이 된다.

그럼 위의 내용을 통해서 DP[N] 값을 구하기 위한, 하나의 정형화된 식을 한번 찾아보자.

DP[N]의 값을 생각해보자. 3가지 연산을 모두 비교해서 그 중 최소횟수를 찾아주면 된다.

먼저, 가장 간단한 3번 연산인 "1을 뺀다" 를 계산해보자. 이는, 역으로 생각하면, N - 1의 값에서 +1을 하는 연산을 한번 더

취하는 경우이기 때문에, DP[N] = DP[N - 1] + 1 이라는 식을 도출할 수가 있다.

1번 연산은, 역으로 생각하면, N / 3 의 값에서, x3 이라는 연산을 한번 더 취하는 경우이기 때문에, 이를 식으로 적어보면

DP[N] = DP[N / 3] + 1 이 된다.

2번 연산도 마찬가지로 계산해보면, DP[N] = DP[N / 2] + 1이 된다.

즉 ! 우리는 이 3가지 값 중에서 최소 값을 저장해주면서 진행하면 된다.

따라서 우리는 최종적으로 다음과 같은 점화식을 구할 수 있다.

DP[N] = Min(DP[N], DP[N - 1] + 1)

DP[N] = Min(DP[N], DP[N / 3] + 1)

DP[N] = Min(DP[N], DP[N / 2] + 1)

소스코드는 위에서 말한 2가지 방법 모두 첨부하겠다.

[ 완전탐색(BFS)을 이용한 소스코드 ]

#include <iostream>
#include <queue>
 
#define endl "\n"
#define MAX 1000000 + 10
using namespace std;
 
int N;
bool Visit[MAX];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(N, 0));
    Visit[N] = true;
    
    while (Q.empty() == 0)
    {
        int Cur = Q.front().first;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (Cur == 1)
        {
            cout << Cnt << endl;
            return;
        }
        
        if (Cur % 3 == 0)
        {
            if (Visit[Cur / 3] == false)
            {
                Visit[Cur / 3] = true;
                Q.push(make_pair(Cur / 3, Cnt + 1));
            }
        }
        if (Cur % 2 == 0)
        {
            if (Visit[Cur / 2] == false)
            {
                Visit[Cur / 2] = true;
                Q.push(make_pair(Cur / 2, Cnt + 1));
            }
        }
        if (Visit[Cur - 1] == false)
        {
            Visit[Cur - 1] = true;
            Q.push(make_pair(Cur - 1, Cnt + 1));
        }
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

[ DP방식을 이용한 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1000000 + 10
using namespace std;
 
int N;
int DP[MAX];    // 해당 인덱스 값을 만들기 위해서 취해야 하는 연산의 최소횟수
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 0; i <= N; i++) DP[i] = 2e9;
}
 
void Solution()
{
    DP[0] = DP[1] = 0;    // 0은 입력의 범위에 해당하지 않고 , 1은 그 자체만으로 1이기 때문에 연산 횟수가 0번이다.
    for (int i = 2; i <= N; i++)
    {
        DP[i] = Min(DP[i], DP[i - 1] + 1);
        if (i % 2 == 0) DP[i] = Min(DP[i], DP[i / 2] + 1);
        if (i % 3 == 0) DP[i] = Min(DP[i], DP[i / 3] + 1);
    }
    cout << DP[N] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}