[BAEKJOON] 백준 17626: Four Squares (C#)

문제 링크

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

 

 

문제

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5^2과 1^2의 합이다; 또한 4^2 + 3^2 + 1^2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125^2 + 6^2 + 1^2 + 1^2라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105^2 + 15^2 + 8^2 + 5^2.

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

 

 

입력

입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.

 

 

출력

출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

 

 

 

통과한 답안

namespace _17626
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] dp = new int[n + 1];

            for (int i = 0; i <= n; i++)
            {
                dp[i] = i;
            }

            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j * j <= i; j++)
                {
                    dp[i] = Math.Min(dp[i], dp[i - j * j] + 1);
                }
            }

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

 

숫자가 주어졌을 때, 해당 숫자를 제곱수의 합으로 나타내는 경우에

최소 몇 개의 제곱수가 필요하는지를 구하는 문제이다.

 

우선 문제를 보고 DP를 이용하여 풀이할 수 있을 것이라 판단하여 접근한 것이 위의 코드인데,

i라는 숫자를 표현하는데 i개의 제곱수(1이 i개)가 필요하다고 dp를 초기화한 후에

 

i보다 작은 제곱수 j * j(jj)를 만들고,

현재의 dp[i]의 값과 새로운 수(i - jj)에 1가지 경우를 추가한 값 중에 작은 것을 취하도록 한다.

예를 들어서 dp[12] = 12로 시작하지만,

j가 1, 2, 3이 들어갈 수 있으며 이는

dp[12] = Math.Min(dp[12], dp[12 - 1 * 1] + 1) = Math.Min(dp[12], dp[11] + 1)

dp[12] = Math.Min(dp[12], dp[12 - 2 * 2] + 1) = Math.Min(dp[12], dp[8] + 1)

dp[12] = Math.Min(dp[12], dp[12 - 3 * 3] + 1) = Math.Min(dp[12], dp[3] + 1)

이러한 방식으로 dp[12]의 값이 갱신되는데,

초기 dp[12]는 12이지만, 위의 과정을 통해서

dp[12] = 2 * 2 + 2 * 2 + 2 * 2 (dp[8] + 1)이 가장 적게 필요하다고 구할 수 있다.

 

 

 

문제에서 제시된 카테고리가 DP가 적혀있어서 DP를 생각하고 풀이한 것이 위의 코드인데,

문제 자체에서는 DP라는 이야기보다는

'모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현될 수 있다'

라는 문장이 있는 것에 힌트를 받아서 구현한 코드가 아래와 같은데,

 

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

            if (IsSquare(n))
            {
                Console.WriteLine(1);
                return;
            }

            for (int i = 1; i * i <= n; i++)
            {
                if (IsSquare(n - i * i))
                {
                    Console.WriteLine(2);
                    return;
                }
            }

            for (int i = 1; i * i <= n; i++)
            {
                for (int j = 1; j * j <= n - i * i; j++)
                {
                    if (IsSquare(n - i * i - j * j))
                    {
                        Console.WriteLine(3);
                        return;
                    }
                }
            }

            Console.WriteLine(4);
        }

        static bool IsSquare(int n)
        {
            int s = (int)Math.Sqrt(n);
            return s * s == n;
        }
    }
}

 

n이 주어졌을 때, 이 n의 제곱근의 정수 부분을 s로 가져와서

s * s가 n을 만족하면 해당 수는 제곱수인 것을 판단할 수 있고,

이 논리를 이용하여 n이 제곱수라면 1을 출력한다.

 

그렇지 않다면 아래와 같이 n에 대해서 제곱수를 하나씩 빼면서

제곱수를 뺀 값이 제곱수인지 확인한다.

for (int i = 1; i * i <= n; i++)
{
    if (IsSquare(n - i * i))
    {
        Console.WriteLine(2);
        return;
    }
}

 

그렇지 않다면 이를 제곱수 2개를 빼고

그 값이 제곱수인지 확인하도록 작성하였다.

for (int i = 1; i * i <= n; i++)
{
    for (int j = 1; j * j <= n - i * i; j++)
    {
        if (IsSquare(n - i * i - j * j))
        {
            Console.WriteLine(3);
            return;
        }
    }
}

 

이 조건도 만족하지 않는다면 4를 출력하도록 작성하였다.

 

문제의 조건에서 최대 4개의 제곱수로 나타낼 수 있다고 하였으므로 작성할 수 있던 코드로

n이 제곱수인지, n에서 제곱수를 1개 뺀 것이 제곱수인지

n에서 제곱수를 2개 뺀 것이 제곱수인지 판단하고

위의 세 조건에서 해결할 수 없다면 4를 출력하도록 작성한 코드로

DP를 이용하지는 않았지만, 문제에서 주어진 조건을 잘 이용한 코드라고 생각한다.