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

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

- 입력 

첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.

 - 출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 - 풀이 

문제 조건을 보면

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

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

3. 1을 뺀다.

이렇게 3가지 조건이 있는데, dynamic programming(동적 계획법)적으로 문제를 접근해 보면, 현재 내가 조사하는 값은 현재 조하사고자 하는 인덱스를 2로 나누고 그 나머지 값의 합과 3으로 나누고 그 나머지의 합의 최솟값이라는 것을 알 수 있다. 

#include <iostream>
#include <algorithm>
void input_faster()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
}
int input()
{
    int N;
    input_faster();
    std::cin >> N;
    return (N);
}
int dp(int x)
{
    if (x <= 1)
        return (0);
    return (std::min((dp(x/2) + 1) + (x % 2) , (dp(x/3) + 1) + (x % 3)));
}
void solve(int N)
{
    std::cout << dp(N);
}
int main()
{
    solve(input());
    return (0);
}