[백준] 알고리즘 1699번 - 제곱수의 합 문제

#include <bits/stdc++.h>
using namespace std;
int dp[100001];

int main() 
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		dp[i] = i;
		for (int j = 1; j * j <= i; j++) {
			if (j * j == i)dp[i] = 1;
			else dp[i] = min((dp[i - j*j] + 1),dp[i]);
		}
	}
	cout << dp[n];
	return 0;
}

1=1^2

2=1^2+1^2 이런식으로 제곱수의 합으로 나타낼 수 있는 최소의 개수를 구하는것이 목표이다.

dp[i] = i 번째 수의 제곱수로 나타낼 수 있는 최소의 개수를 저장한다.