개발공부/algorithm
[백준][python] 17626 - Four squares
so.py
2021. 6. 6. 21:01
문제
- 백준 17626: Four Squares
- Silver V
- 문제링크
17626번: Four Squares
라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1
www.acmicpc.net
N = int(input())
min_sum = 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):
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)