BOJ 1463 c++

BOJ 1463 1로 만들기

백준 1463

DP는

BOJ 1463번이 대표적인 문제.

BOJ 1463번 풀이

#include <bits/stdc++.h>
using namespace std;

int n;
int d[1000005];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    d[1] = 0;
    for (int i = 2; i <= n; i++) {
        d[i] = d[i - 1] + 1;
        if (i % 2 == 0)
            d[i] = min(d[i], d[i / 2] + 1);
        if (i % 3 == 0)
            d[i] = min(d[i], d[i / 3] + 1);
    }
    cout << d[n];
}