백준/Class3
[백준] Class3-Four Squares C++ 17626번
taene_
2023. 10. 10. 14:26
https://www.acmicpc.net/problem/17626
17626번: Four Squares
라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1
www.acmicpc.net
#include<iostream>
#include<algorithm>
using namespace std;
int dp[50001] = { 0,1,2,3,1, };
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
for (int i = 4; i <= n; i++)
{
dp[i] = dp[i - 1] + 1;
for (int j = 1; j * j <= i; j++)
{
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
}
cout << dp[n];
return 0;
}접근방법: 규칙찾기, DP문제
생각할 점: 제곱의 합들로 다루는 문제이므로 점점 증가하는 해당 i에 제곱수를 뺀 값의 dp값을 생각해서 점화식을 생각해보자.