[Beakjoon][Sliver][17626] For Squares

[문제 바로가기] : https://www.acmicpc.net/problem/17626

For Squares 문제

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52.
자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

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

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

문제 풀이

Dynamic Programming 문제이다.
먼저 문제에 따라 어떤 자연수를 제곱수의 합으로 나열해 본다.

위의 표에서 알 수 있는 것은 i가 제곱이면 제곱수로 표현가능한 최소 개수는 1이란 것과 i보다 작은 제곱수로 빼면 이미 구해진 제곱수의 합들로 나머지가 구성된다는 것이다.

EX) i = 4인 경우

먼저 4보다 작은 경우는 어떻게 되나 생각해보자.

i이 1인 경우에는 $1^2$외에는 존재하지 않는다. 따라서 $DP_{1}=1^2$

$DP_{i}$
위에서 정의한 초기값은 최소가 아니므로 최소값을 구해준다.

i이 4이면, i보다 작거나 같은 제곱수는 $1^2$, $2^2$이다.

$1^2$으로 표현하면,

$4 = 1^2+1^2+1^2+1^2$

$2^2$을 포함하면,

$4 = 2^2$

$1^2+1^2+1^2+1^2$

따라서 $DP_{i}=\min(DP_{i},\space DP_{i-j^2}+1) \space\space (DP_{0}=0,\space DP_{1}=1,\space 1 \leq i \leq N,\space 1 \leq j^2 \leq i)$ 이다.
1을 더하는 이유는 2이상의 제곱수가 다른 제곱수를 대신하기 때문이다.

EX) i = 12인 경우

$DP_i$

i가 12이면, i보다 작거나 같은 제곱수는 $1^2$, $\space2^2$, $\space3^2$이다.
$1^2$으로 표현하면,

$12 = 1^2+1^2+1^2+1^2+1^2+1^2+1^2+1^2+1^2+1^2+1^2+1^2$

$2^2$을 포함하면,

$12=2^2+1^2+1^2+1^2+1^2+1^2+1^2+1^2+1^2$

$3^2$을 포함하면,

$12 = 3^2+1^2+1^2+1^2$

이다.

초기값은 $DP_{i}=DP_{i-1}+DP_{1}\space\space(DP_{0} = 0,\space DP_{1}=1,\space1 \leq i \leq N)$

$DP_{12}=DP_{11}+DP_{1}=3+1=4$

이는 $3^2+1^2+1^2+1^2$

$i=12,\space j=2,\space 3$

$DP_{i}=\min(DP_{i},\space DP_{i-j^2}+1) \space\space (DP_{0}=0,\space DP_{1}=1,\space 1 \leq i \leq N,\space 1 \leq j^2 \leq i)$

$DP_{12}=4 > DP_{8}+1=3$

이는 $2^2+2^2+2^2$

$DP_{12}=3$

$DP_{i}=\min(DP_{i},\space DP_{i-j^2}+1) \space\space (DP_{0}=0,\space DP_{1}=1,\space 1 \leq i \leq N,\space 1 \leq j^2 \leq i)$

$DP_{12}=3 < DP_{3}+1=4$

문제 정답

C++ 17

#include <iostream>
#include <algorithm>

using namespace std;

int DP[50001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N;
	cin >> N;

	DP[1] = 1;

	for (int i = 1; i <= N; i++)
	{
		DP[i] = DP[1] + DP[i - 1];
		for (int j = 2; j * j <= i; j++)
		{
			DP[i] = min(DP[i], 1 + DP[i - j * j]);
		}
	}

	cout << DP[N];
}

JAVA 11

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(bufferedReader.readLine());
        int[] DP = new int[N + 1];

        DP[0] = 0;
        DP[1] = 1;

        for(int i = 1; i <= N; i++) {
            DP[i] = DP[i - 1] + DP[1];
            for(int j = 2; j * j <= i; j++) {
                DP[i] = Math.min(DP[i], DP[i - j * j] + 1);
            }
        }

        System.out.println(DP[N]);
    }
}

C# 9.0(.NET)

using System;

class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine() ?? string.Empty);
        int[] DP = new int[N + 1];

        DP[1] = 1;

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

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