[백준] 17626 - Four Squares

1. 문제

17626번: Four Squares

2. 개요

주어진 자연수 n을 제곱수만의 합으로 나타낼 때 그 제곱수들의 최소 개수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

먼저 최소 개수를 저장할 배열을 만든 뒤 모든 값을 4로 초기화한다.

제곱수인 경우에는 1로 갱신해준다.

어떤 자연수 n은 무조건 제곱수만의 합으로 나타낼 수 있기 때문에 n을 이루는 제곱수의 최소 개수는 n보다 작은 수를 만드는 제곱수의 최소 개수 + 어떤 제곱수로 나타낼 수 있다.

이를 dp[n] = dp[n - x] + 1로 나타낼 수 있다.

이를 이용해 dp테이블을 채운 뒤 답을 출력한다.

3-2. Python

import sys

N = int(sys.stdin.readline())
dp = [4 for i in range(N + 1)]
squares = []
    

for i in range(1, N + 1):
    if i * i <= N:
        dp[i * i] = 1
        squares.append(i * i)

    for j in range(len(squares)):
        if squares[j] >= i:
            break
        
        if dp[i] > dp[i - squares[j]] + 1:
            dp[i] = dp[i - squares[j]] + 1

print(dp[N])

3-3. C#

namespace boj_17626
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            int[] dp = new int[N + 1];
            Array.Fill(dp, 4);

            List<long> squares = new List<long>();

            for (long i = 1; i < N + 1; i++)
            {
                if (i * i <= N)
                {
                    dp[i * i] = 1;
                    squares.Add(i * i);
                }

                for (int j = 0; j < squares.Count; j++)
                {
                    if (squares[j] >= i)
                        break;

                    if (dp[i] > dp[i - squares[j]] + 1)
                        dp[i] = dp[i - squares[j]] + 1;
                }
            }

            Console.WriteLine(dp[N]);
        }
    }
}