문제 ❌

제곱수의 합

후기 및 분석

일단 점화식을 생각을 도저히 못했었음..

for (int i = 1; i <= n; ++i)
{
	for (int j = 1; j * j <= i; ++j)
	{
		cache[i] = min(cache[i], cache[i - j * j] + 1);		
    }
}

위의 코드에서 cache의 인덱스에다가 i - j * j 이런식으로 인덱스를 넣는다거나

cache의 인덱스가 만약 3 cache[3]일 경우

3일때의최소 제곱수를 뜻한다고 cache를 정의하는 부분이라던지...

1시간도 넘겼고 다른사람들 코드 보면서 보니까 어느정도는 이해가 됬었음.

https://yabmoons.tistory.com/83
여기가 설명 제일 좋은듯?

cpp 코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define MAX 100001
#define endl "\n"

int cache[MAX];
int arr[MAX];

int main()
{	
	int n;
	cin >> n;

	for (int i = 1; i <= n; ++i) cache[i] = i;

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j * j <= i; ++j)
		{
			cache[i] = min(cache[i], cache[i - j * j] + 1);
		}
	}
	
	cout << cache[n];

	return 0;
}