백준 1699 / 제곱수의 합

다이나믹 프로그래밍 문제.

점화식은 i^2이 N을 구성하는 어떠한 한 제곱수라고 가정할때

D[N] = min (D[N-i^2]) +1

어렵다.

코드

#include<stdio.h>
#include<iostream>
#include <math.h>
using namespace std;
 
int main() {
    int n;
    int cnt = 0;
    cin >> n;
 
    int d[100001];
 
    d[0] = 0;
    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];
}