[boj] 17626_Four squares_python

문제링크

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

17626번: Four Squares

 

---

문제설명

문제

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

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

 

입력

1. 자연수  n 

 

출력

1. 합이 n과 같게 되는 제곱수들의 최소 개수 ( 개수 <= 4 ) by. 라그랑주의 네 제곱수 정리

 

제한

• 1 <= n <= 50,000
• 주어지는 모든 수는 자연수이다.

---

문제풀이

조건 1 : 라그랑주 네 제곱수 정리에 의해. 모든 수는 최대 4개의 제곱수의 합으로 이루어져있다.

따라서, 1*1 + ( i - 1*1 )와 4중에 더 작은 수를 answerList에 우선적으로 할당해준다.

 

조건2. 조건1의 일반화

조건1에서는 i - 1*1(1의 제곱)에 해당하는 결과만 생각해주었다.

이를 i까지의 경우로 확장시켜서 계산해준 것이 조건 2이다.

 

그리고 이 과정에서 조건1. 의 시간 복잡도는 O(n), 조건2에서의 시간 복잡도는 O( log ₂ n(n-1)/2)가 되므로

전체 시간 복잡도 역시 구할 수 있을 것이다.

---

# 시간 복잡도 : O(nlog₂ ( n(n-1)/2 )) # ①과 ② 과정에 따라 결정
# 공간 복잡도 : 0(n) => n의 범위가 1~50000이기에 answerList의 크기
import sys # 빠른 입력
from math import sqrt # 루트 계산을 위함

n = int(sys.stdin.readline().strip()) # n을 입력받는다.
answerList = [0 for i in range(n+1)] # answerList를 작성한다.

answerList[1] = 1 # 초기 answerList값. 1로 설정
# ①번 loop : 2 ~ n까지의 수의 제곱수의 합을 찾는다.
for i in range(2, n+1):
    # 라그랑주 네 제곱수 정리 : 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다
    # 조건1. 1² + (i - 1)일 때의 개수 vs 최대치 : 4
    answerList[i] = min(1 + answerList[i-1], 4)
    # 조건2. ②번 loop 1 ~ √i 만큼의 범위를 돈다.
    # 조건1 에서 구한 answerList[i]와 1 ~ √i의 경로를 돌았을 때의 결과를 비교한다.
    # i - j*j를 하고 +1을 해줬는데 여기서 +1이 j*j를 의미한다.
    # 시간 복잡도를 조금 더 줄여주기 위해 루트를 취해주었다.
    # j의 범위가 1 ~  √i라면, j*j의 범위는 1~i까지가 된다.
    # 즉, 제곱수를 더 효과적으로 구하기 위한 트릭.
    answerList[i] = min(answerList[i], min(answerList[i-j*j]+1 for j in range(1, int(sqrt(i)+1))))

print(answerList[n])

 

---

참고 레퍼런스

1. https://doodle-ns.tistory.com/32

[노트] 모든 약수를 구하는 알고리즘은 O(sqrt(n))이다.

2. https://jjycjnmath.tistory.com/295 

[퍼온글] 라그랑주의 네제곱수 정리(Four Square Theorem)와 그 증명