1699번: 제곱수의 합

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


$O(n\sqrt{n})$

dp[i]=min(j*j<=i)(dp[i-j*j]+1)

답은 dp[n]

#include<stdio.h>
#include<algorithm>
using namespace std;
int n, dp[100001];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        dp[i] = 1e5;
        for (int j = 1; j*j <= i; j++) dp[i] = min(dp[i], dp[i - j*j] + 1);
    }
    printf("%d", dp[n]);
    return 0;
}