(c++)백준 1699번: 제곱수의 합

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

1699번: 제곱수의 합

※점화식※

dp[i] : i를 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수

dp[x] = dp[x-j^2] + 1 (j^2는 x값에 가장 가까운 제곱수, 자연수 x-j^2에 j^2 더한 항의 수)

 

#include <iostream>
using namespace std;

int N;
long long dp[100001];

void DP() {
	for (int i = 1; i <= N; i++) {
		//i에 가장 가까운 j^2 찾을 때까지
		for (int j = 1; j*j <= i; j++) {
			//자연수 i를 처음 보거나 i-(j^2)번째 dp에 j^2항 하나 더 붙인 게 기존 dp[i]보다 작으면
			if (dp[i] == 0 || dp[i] > dp[i - j * j] + 1) {
				dp[i] = dp[i - j * j] + 1;
			}
		}
	}
	cout << dp[N] << endl;
}

int main() {
	cin >> N;
	DP();
	return 0;
}