문제

풀이1 - DP

문제에 의하면, 어떠한 자연수는 반드시 넷 이하의 제곱수의 합으로 이루어져 있다.

즉, $n=a^2+b^2+c^2+d^2$가 반드시 성립하게 된다. 이 때, n은 자연수이고 a,b,c,d는 정수이다.

이를 다시 표현하면, 자연수 n에서 제곱수의 합을 빼주었을 떄에도 제곱수의 합으로 이루어져 있어야 한다.
$n-a^2 = b^2+c^2+d^2 \text{ or } n-a^2-b^2 = c^2+d^2$

그러므로, 어떠한 자연수 $n$에 대해서 $n$보다 작은 제곱수를 빼주었을 때$(n-k^2)$, 그 수는 반드시 어떠한 제곱수들의 합일 것이므로 $n-k^2$를 구성하고 있는 제곱수의 개수보다 한개 많은 제곱수로 이루어져 있다고 볼 수 있다.

해당 문제에서는 제곱수가 최소의 개수로 이루어져 있는 경우를 찾아야하기 때문에, n보다 작은 제곱수를 빼준 모든 경우의 최소값을 구한뒤 1을 더해주면 해결 가능하다.

예를 들어, 8이라는 수가 최소 몇개의 제곱수로 이루어져있는지 구하기 위해서 8보다 작은 제곱수인 4와 1을 각각 8에서 빼주면, 가능한 $n-k^2$은 4와 7이고 이 두수는 $2^2$, $2^2+1^2+1^2+1^2$으로 분해할 수 있고 각각 1개, 4개의 제곱수로 구성되어 있는 것을 확인할 수 있다.

따라서, 8을 구성하는 제곱수의 최소 개수는 $2^2+2^2$인 2개로 구할 수 있다.

이를 코드로 구현하면 다음과 같다.

import math
n = int(input())
dp = [0]*(n+1)
dp[1]=1
for i in range(2,n+1):
    _min=1e9
    for j in range(1,int(math.sqrt(i))+1): # i보다 작은 제곱수(j**2)를 뺌
        _min = min(_min, dp[i-j**2]) # 'i-j**2'인 경우의 최소 제곱수의 개수
    dp[i]=_min+1
print(dp[n])

하지만, 위 풀이는 python3를 사용해 테스트를 진행할 경우에 시간초과가 발생한다. 단, PyPy3를 사용하면 통과가능

풀이2 - Brute Force

해당 풀이를 사용하면 python3를 사용하더라도 통과할 수 있다.

import math
# 브루트포스
n = int(input())

def is_square(num):
    if math.sqrt(num)==int(math.sqrt(num)):
        return True
    else:
        return False

_min=4
if is_square(n): # 1. n이 제곱수인 경우
    _min=1
else:
    for i in range(int(math.sqrt(n)),0,-1):
        # 2. 두 제곱수의 합인 경우(=2) / 제곱수를 뺀 값이 제곱수인 경우
        if is_square(n-(i**2)):
            _min=2
            break
        else: # 3. 세 제곱수의 합인 경우(=3)
            for j in range(int(math.sqrt(n-i**2)),0,-1):
                if is_square(n-(i**2)-(j**2)):
                    _min=3
                    break

print(_min)