#391 백준 파이썬 [17626] Four Squares

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

 

SOLUTION

라그랑주의 네 제곱수 법칙의 증명은 참조 (https://ko.wikipedia.org/wiki/%EB%9D%BC%EA%B7%B8%EB%9E%91%EC%A3%BC_%EB%84%A4_%EC%A0%9C%EA%B3%B1%EC%88%98_%EC%A0%95%EB%A6%AC)

하지만 우리는 해당 식을 증명하고자 하는 게 아니기 때문에 3번의 for문을 통해서 제곱수들의 최소 개수를 추려내볼 수 있다.

큰 숫자부터 차례대로 모든 숫자를 대입해 보는 것. 그리고 다음 숫자로 넘어가는 것

단 시간을 빠르게 하기 위해 range를 적절하게 조정[A**0.5 ~ (A//4)**0.5]해준다.

PYTHON CODE

n = int(input())
min_sum = 4 #최대는 4라고 증명되어있다, 아래 3중 for문에서 걸리지 않는다면 답은 4
for a in range(int(n**0.5), int((n//4)**0.5), -1): #가능한 최소한의 범위로 축소해준다
    if a*a == n:
        min_sum = 1 #최소의 숫자일 경우
        break
    else:
        temp = n - a*a
        for b in range(int(temp**0.5), int((temp//3)**0.5), -1): #남은 숫자는 3이니까 3으로 나누어줌
            if a*a + b*b == n:
                min_sum = min(min_sum, 2)
                continue
            else:
                temp = n - a*a - b*b
                for c in range(int(temp**0.5), int((temp//2)**0.5), -1):
                    if n == a*a + b*b + c*c:
                        min_sum = min(min_sum, 3)
                
print(min_sum)