[ BOJ/C# ] 17626 Four Squares

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

17626번: Four Squares

DP 문제이다. 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다는 증명은 굉장히 흥미로웠다. 

n==1부터 n==7까지는 n이 제곱수이면 1, 이후 +1씩 증가했다. 

하지만 n==8부터는 그동안과 다른 패턴들이 나온다. 

이는 일정한 규칙으로 보이지 않고 가장 가까운 제곱수의 합을 포함하지 않은 경우,

최소 개수가 나올 경우가 존재한다.

따라서 최소 개수를 (n-1일 때의 값+1)로 설정하고, 본인보다 작은 제곱근들을 뺀 경우들과 비교하여 최소 개수를 구한다. 

using System;

namespace B17626
{
    class Program
    {
        static int GetSquresN(int n)
        {
            int[] array = new int[n + 1];
            if (n <= 3) return n;
            else
            {
                array[1] = 1;
                array[2] = 2;
                array[3] = 3;
                for (int i = 4; i <= n; i++)
                {
                    if (MathF.Sqrt(i) % 1 == 0) array[i] = 1;
                    else
                    {
                        int k = (int)MathF.Truncate(MathF.Sqrt(i));
                        int min = array[i - 1] + 1;
                        for (int j = 1; j <= k; j++)
                            if (min > (array[i - (j * j)])) min = (array[i - (j * j)]);
                        array[i] = min + 1;
                    }
                }
                return array[n];
            }
        }
        static void Main()
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            int n = int.Parse(sr.ReadLine());
            int result = 0;

            //하나의 제곱수로만 이루어질 경우
            if (MathF.Sqrt(n) % 1 == 0) result = 1;
            //아닌 경우
            if (result == 0) result = GetSquresN(n);
            sw.Write(result);
            sr.Close();
            sw.Flush();
            sw.Close();
        }
    }
}