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


DP[i] = (i를 만드는 데 걸리는 최소 횟수) 라고 하면
여러 특성에 의해서 식을 간단히 세울 수가 있음. 이를 Naive 하게 구현하면 O(N^2)임


여기서 특징을 하나 더 잡으면 O(N lg N) 가능
귀찮으니까 N^2 풀이 올림


#include <cstdio>
#include <algorithm>

constexpr int MAXN = 1040;

int dp[MAXN];

int main() {
    int N;
    scanf("%d", &N);

    dp[1] = 0;
    for (int i = 2; i <= N; ++i) dp[i] = i;

    for (int i = 2; i < N; ++i) {
        for (int j = i + 1; j < MAXN; ++j) {
            const int sub = i - (j - 1) % i - 1;
            const int jj = j + sub;
            dp[j] = std::min(dp[j], dp[i] + jj / i + sub);
        }
    }

    printf("%d", dp[N]);
}