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

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

( 문제 바로가기 )

( 문제를 다시 푸는 과정에서 보다 상세한 설명을 다시 포스팅 해놓았습니다. 이 글을 읽으셔도 무관하지만, 보다

  구체적인 설명을 원하시는 분들은 아래의 링크를 타고 가시면 됩니다 ! )

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

[ 문제설명 ]

- 입력으로 정수가 주어지고, 그 정수를 

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

  2. 2로 나누어 떨어지면 2로 나눈다.

  3. 1을 뺀다.

  위 3가지 조건을 이용해서 주어진 숫자를 1로 만들어 주면 된다.

- 주어진 숫자를 1로 만드는 가장 최소 횟수를 출력시키면 된다.

[ 문제풀이 ]

1) 가장 기본식을 찾아보면 Arr[0] = Arr[1] = 0이 된다.

   왜냐하면, 0은 입력 범위에 해당하지 않고, 1은 아무런 행동을 취하지 않아도 1이기 때문에 값이 0이 된다.

2) 1)의 식에서 Arr[a] 의 의미 = 'a를 1로 만드는데 걸리는 횟수' 이다. 

   Arr[2] = 1이 되고, Arr[3] = 1이 된다.

   그렇다면 Arr[4] = ???

   Arr[4]의 경우 N-1과정을 통해서 Arr[3]으로 만들어주고(1회) + Arr[3] = 1 이므로 총 2회가 된다.

   혹은 N/2과정을 통해서 Arr[2]로 만들어주고(1회) + Arr[2] = 1 이므로 총 2회가 된다.

   N/3의 과정은 조건에 부합하지 않으므로 불가능하다. 즉 답은 2회가 된다.

3) 2)의 과정을 통해 생각해볼 수 있는 점화식은 " N - 1을 1로 만들 수 있는 최소 횟수 + 1회"  or

   " N / 2를 1로 만들 수 있는 최소 횟수 + 1회" or " N / 3을 1로 만들 수 있는 최소 횟수 + 1회" 가 된다.

4) 3)에서 말한 내용을 식으로 옮겨보면 Arr[N] = Arr[N - 1] + 1 or Arr[N / 2] + 1 or Arr[N / 3] + 1이 된다.

5) 4)를 코드로 그대로 구현하면 되는데, 일반 DP풀이와 같이 반복문을 N번까지 반복시켜주면 되고, 4)에서 말한 식 중에서

   2로 나누거나 3으로 나누는 경우에는 나누어 떨어져야한다 라는 조건이 있으므로 조건문으로 충족시켜 주면 된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 1000000 + 1
using namespace std;
 
int N;
int Arr[MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    Arr[0] = 0;
    Arr[1] = 0;
 
    for (int i = 2; i <= N; i++)
    {
        Arr[i] = Arr[i - 1] + 1;
        if (i % 2 == 0) Arr[i] = Min(Arr[i], Arr[i / 2] + 1);
        if (i % 3 == 0) Arr[i] = Min(Arr[i], Arr[i / 3] + 1);
    }
}
 
void Solve()
{
    Input();
    Solution();
 
    cout << Arr[N] << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}