# 백준 : 1로 만들기(1463)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/edit/master/bj_1463_makeone)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int arr[1000001];
int makeone(int num);

int main(void) {
    // insert code here...
    int num;
    cin>>num;
    cout<<makeone(num)<<endl;
    return 0;
}

int makeone(int num)
{
    arr[1] = 0;
    if(num > 1) {
        for(int i=2; i<=num; i++)
        {
            arr[i] = arr[i-1] + 1;  //arr[i]-1 = arr[i-1]
            if(i % 3 == 0)  arr[i] = min(arr[i], arr[i / 3] + 1);
            if(i % 2 == 0)  arr[i] = min(arr[i], arr[i / 2] + 1);
        }
    }
    return arr[num];
}

풀이

DP를 이용해서 문제를 푸는 연습을 하고 있는데, 한가지 느끼는 점은
'DP는 단순(Simple)해야 한다'는 점이다.

문제는 3가지 조건을 제시한다.
1. 주어진 숫자에서 1을 빼거나
2. 3으로 나누어지면 3으로 나누거나
3. 2로 나누어지면 2로 나누거나
셋 중 하나를 이용해서 주어진 숫자를 1로 만드는 가장 적은 횟수를 출력하는 문제다.

그러면 1은? 0번만에 1이 되는거라고 보면 되고.
그러면 2는? 2로 나누어도 1번만에 1이 되고, 1을 빼도 1번만에 1이 되겠지
그러면 3은? 3으로 나누면 1번만에 1이 되지만, 1을 빼면 2가 되고 거기서 1번만에 1이 되니까 총 2번만에 1이 될 것이다. 이 중 더 적은 횟수는 1이니까 1이 되겠지.
그러면 4는? 
2로 나누는 횟수 1에 나눈 결과인 2에서 1이 되는 횟수 1이므로 총 2번.
혹은 1을 빼는 횟수 1에 결과인 3에서 1이 되는 횟수가 2 또는 1인데 이중 최소값은 1이었으니까 총 2번.

이를 식으로 표현하면 다음과 같다.
우선 각 숫자에서 1이 되는 최소 횟수를 저장하는 배열을 arr이라고 하자
그리고 주어진 숫자에서 1을 뺴는 것은 2로 나누어지나 3으로 나누어지나 상관없이 가능하니까
arr[number] - 1 = arr[number-1]이니까, 결국 arr[number] = arr[number - 1] + 1
이 되겠지.

우리는 이제 arr[1]부터 arr[number]까지 bottom-top 형식으로 쭉 계산하면 된다.
계산과정에서 필요한 값들은 arr[이전번호]에서 가져다 쓰면 된다.
그런데 우리는 arr[1] = 0인 것은 알고 있을 뿐만 아니라, arr[1]은 arr[0] + 1로 계산할 수 없으니까
2부터 쭉 올라가면서 계산해보면 된다.

그러면 가볍게 결과 값을 도출할 수 있다.
DP 쉽지 않다. 생각하는 방법을 길러야 하는 것 같다!