[BOJ/C++] 1463 1로 만들기

동적 계획법을 이용해 문제를 해결할 수 있습니다.

X는 3가지 연산을 할 수 있습니다.

1. 3으로 나누어 떨어지는 경우 3으로 나눈다
2. 2로 나누어 떨어지는 경우 2로 나눈다
3. 1을 뺀다

기본적으로 1을 빼는 연산을 한 후 2로 나누어 떨어지는 경우, 3으로 나누어 떨어지는 경우에서 최솟값을 고르면 됩니다.

$min(DP[i-1]+1, DP[i/2]+1, DP[i/3]+1)$

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;

static int DP[1000001] = {};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;

    DP[1] = 0;
    DP[2] = 1;
    DP[3] = 1;


    for(int i=4; i<=N; i++)
    {
        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];
    


    return 0;
}