[BOJ] 1463 : 1로 만들기

문제

[BOJ] 1463 : 1로 만들기

memo[n] = memo[n-1] + 1,

memo[n] = memo[n/2] + 1,

memo[n] = memo[n/3] + 1

중 제일 작은 수!

코드

#include<iostream>
#include<algorithm>
using namespace std;
int memo[1000001], n;
int main() {
    scanf("%d", &n);
    memo[1] = 0;
    for (int i = 2; i <= n; i++) {
        memo[i] = memo[i - 1] + 1;
        if (i % 2 == 0) {
            memo[i] = min(memo[i / 2] + 1, memo[i]);
        }
        if (i % 3 == 0) {
            memo[i] = min(memo[i / 3] + 1, memo[i]);;
        }
    }
    printf("%d",memo[n]);
    return 0;
}