[백준][DP] 제곱수의 합

1. 문제 주소

1699번: 제곱수의 합

2. 문제

자연수 N을 제곱수들의 합으로 나타낼 때 최소 항의 개수를 구하는 문제이다. 가장 마지막에 더해지는 숫자가 무엇인지 확인하면 쉽게 풀 수 있다. 예를 들어 i를 제곱수의 합으로 나타낼 때 가장 마지막에 더해지는 숫자가 4이면 i-4를 나타내는 최소 항의 개수에 1을 더해주면 된다.

 

3. 소스코드

#include <iostream>
using namespace std;
int num[100001];
 
int main() {
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        num[i] = i;
        for (int j = 1; j * j <= i; j++) {
            if (num[i] > num[i - j * j] + 1)
                num[i] = num[i - j * j] + 1;
        }
    }
    cout << num[n] << '\n';
    return 0;
}