[C++] BOJ 1463번: 1로 만들기

문제 링크

문제 풀이

처음으로 풀어본 dp 문제였다. 문제에서는 n을 1로 만드는 최소 횟수를 구하도록 하였으나 아래의 풀이에서는 반대로 1을 n으로 만드는 최소 횟수를 구하였다.

코드

#include <bits/stdc++.h>

using namespace std;

int n;

int calced[1000004];

void check(int num)
{
    if (num <= n)
    {
        if (num % 6 == 0)
        {
            calced[num] = min(min(calced[num / 3], calced[num / 2]), calced[num - 1]) + 1;
        }
        else if (num % 2 == 0)
        {
            calced[num] = min(calced[num / 2], calced[num - 1]) + 1;
        }
        else if (num % 3 == 0)
        {
            calced[num] = min(calced[num / 3], calced[num - 1]) + 1;
        }
        else
        {
            calced[num] = calced[num - 1] + 1;
        }
        check(num + 1);
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    calced[0] = -1;
    check(1);

    cout << calced[n] << '\n';

    return 0;
}