C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 1699번:제곱수의 합 답

//O + O + ... + j^2 = i일 때..

//D[i] = 합의 최소 개수

//i-j^2 = O+O+O...+O

//그러므로 D[i] = min(D[i],D[i-j^2]+1)

#include <iostream>
#include <algorithm>
using namespace std;
int D[100001];
int main() {
    
    int N;
    cin >> N;
    
    for (int i = 1; i <= N; i++)
    {
        D[i] = i;
        for (int j = 1; j*j <= i; j++)
        {
            if (D[i] > D[i - j*j] + 1)
            D[i] = D[i - j*j] + 1;
        }
    }
    cout << D[N];
}