백준 : 제곱수의 합 C++ (DP 연습!!)

www.acmicpc.net/problem/1699

1699번: 제곱수의 합

풀이 및 후기

 DP는 너무 어렵다

 

1. 일단 모두 1만 써서 더하는 경우는 항의 수가 자기 자신이므로 그것으로 초기화!

2. 그다음에 본인보다 작은 제곱수를 뺀 모든 경우에서의 DP값들 중 최솟값을 구하기

 

 

#include <iostream>
#include <queue>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	int n;
	int cnt = 0;
	cin >> n;
	int dp[100000];

	dp[1] = 1;

	//다 1로만 해서 더하는거
	for (int i = 0; i <= n; i++)
		dp[i] = i;

	for (int i = 2; i <= n; i++)
	{
		for (int j = 2; j*j <= i; j++)
		{
			//자기보다 제곱수들 한개 썼을때를 모두 비교해서 그중 젤 작은거로!!
			dp[i] = min(dp[i], dp[i - j * j] + 1);
		}
	}
	cout << dp[n] << endl;
	return 0;
}