BOJ17626 Four squares

문제

코드

#include <iostream>
#include <cmath>
#include <math.h>
using namespace std;

int num[50001] = {
    0,
};
int n;

void solve();

int main()
{
    cin >> n;

    solve();

    cout << num[n];

    return 0;
}

void solve()
{
    for (int i = 1; i <= n; i++)
    {
        int min = 9999;
        int temp, count;

        // 제곱근은 모두 1로
        if ((int)sqrt(i) * sqrt(i) == i)
        {
            num[i] = 1;
            continue;
        }

        for (int j = sqrt(i); j >= 1; j--)
        {
            count = 0;

            temp = num[i - j * j] + 1;
            if (temp < min)
                min = temp;
        }

        num[i] = min;
    }
}

풀이

제곱근들은 모두 1개로 초기화가 가능하고
제곱근들의 수 이전의 경우의 수에 +1을 해주고, 최솟값만 배열의 값에 넣어준다.

제곱근들에서 해당하는 숫자의 갯수와, 규칙은 찾았지만, 그 이하의 숫자들을 구현해내는데는 실패했다.
역순으로 조사하는 방법과 temp = num[i - j * j] + 1; 에서 제곱근을 다시 풀어 배열에 값을 넣어주는 방법을 알게됐다.