[백준] 17626. Four Squares (다시 풀어보기)

DP로 푸니깐 무조건 시간초과가 난다....

import sys
import math
n=int(sys.stdin.readline())
dp=[0]*(n+1)
dp[1]=1
for i in range(2,n+1): #2부터 n까지
    square=1e9 #무한의 수
    root=int(math.sqrt(i)) #i의 제곱근
    for j in range(1,root+1): #j**2<=i일때까지
        square=min(square,dp[i-(j*j)]) # square=dp[i-(j*j)]
    dp[i]=square+1
print(dp[n])

문장 첫째줄을 제대로 안 읽어서 못푼 문제...

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 

브루투포스로 풀면 된다.

import sys
import math
n=int(sys.stdin.readline())
root=int(math.sqrt(n))
def four_squares(n):
    if math.sqrt(n)==root: #n이 제곱수일 경우
        return 1
    for i in range(1,root+1): #n-i^2이 제곱수일 경우
        if int(math.sqrt(n-i**2))==math.sqrt(n-i**2):
            return 2
    for i in range(1,root+1): #n-i^2-j^2이 제곱수일 경우
        for j in range(1,int(math.sqrt(n-i**2))+1):
            if int(math.sqrt(n-i**2-j**2))==math.sqrt(n-i**2-j**2):
                return 3
    return 4
print(four_squares(n))