1699번 제곱수의 합

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

knapsack(냅색) 문제

#include <bits/stdc++.h>
 
using namespace std;
 
int dp[100100], n, sq;
 
int dfs(int cap, int cnt)
{
    if (cap == n) return dp[cap] = cnt;
    if (cap > n) return 2e9;
 
    int & ret = dp[cap];
    if (ret != -1) return ret;
    ret = 2e9;
 
    for (int i = 1; i <= sq; i++) {
        ret = min(ret, dfs(cap + i*i, cnt + 1));
    }
 
    return ret;
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
    fill(dp, dp + 100100, -1);
    scanf("%d", &n);
    sq = sqrt(n);
    printf("%d\n", dfs(0, 0));
 
    return 0;
}