백준 - 17626번 Four Squares python 문제풀이 [Hellfer]

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

17626번: Four Squares

🔷 알고리즘 분류 - 다이내믹 프로그래밍, 브루트포스 알고리즘 

난이도 - 실버 3

라그랑주의 네 제곱수 정리(Lagrange's Four-Square Theorem)는 프랑스의 수학자 라그랑주가 1770년에 제시한 것으로 모든 자연수를 넷 혹은 그 이하의 제곱수의 합으로 나타낼 수 있다는 정리입니다. 

수식으로 표현하면 다음과 같습니다.

 

∀n ∈ N, ∃a, b, c, d ∈ Z, n = a² + b² + c² + d²

 

이는 모든 자연수 n에 대하여, 정수 a, b, c, d가 존재하여 n은 a의 제곱과 b의 제곱, c의 제곱, d의 제곱의 합으로 표현될 수 있다는 뜻입니다.

🔶틀린 문제 풀이 - 다이내믹 프로그래밍이용(시간초과)

# 입력값 n을 받습니다.
n = int(input())

# '라그랑주의 네 제곱수 정리'에 따라, 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있으므로, 
# dp 배열을 5로 초기화합니다. dp[0]의 경우 0을 표현하는데 제곱수는 필요하지 않으므로 0으로 초기화합니다.
dp = [5]*(n+1)
dp[0] = 0

# i는 사용되는 제곱수의 기본 단위를 의미합니다. i가 1부터 √n까지 변하게 됩니다.
for i in range(1, int(n**0.5)+1):
    # i의 제곱부터 n까지의 수를 확인합니다.
    for j in range(i*i, n+1):
        # j를 표현하는데 필요한 최소 제곱수의 개수(dp[j])와 j에서 i의 제곱을 뺀 수를 표현하는데 필요한 최소 제곱수의 개수(dp[j-i*i]) + 1 중 더 작은 값을 선택합니다.
        dp[j] = min(dp[j], dp[j-i*i]+1)

# n을 표현하는데 필요한 최소 제곱수의 개수를 출력합니다.
print(dp[n])

 

해당 코드는 보통 O(n*sqrt(n))의 시간 복잡도를 가지며, 대부분의 경우에는 충분히 빠른 속도로 실행됩니다. 

 

하지만 입력값 n이 매우 클 경우에는 시간 초과가 발생할 수 있습니다.

 

for i in range(1, int(n**0.5)+1):  # i는 1부터 √n까지
    for j in range(i*i, n+1):  # j는 i의 제곱부터 n까지
        dp[j] = min(dp[j], dp[j-i*i]+1)

 

예를 들어, n이 18이라고 가정해 보겠습니다.

 

여기서 i는 제곱수의 기본 단위를, j는 현재 계산하고 있는 수를 나타냅니다.

i가 1일 때, j는 1부터 18까지 변하며, dp [j]는 dp [j]와 dp [j-1] + 1 중 작은 값으로 갱신됩니다. 

 

이때, dp [j-1] + 1은 j를 1의 제곱으로만 표현했을 때의 제곱수의 개수를 나타냅니다.

i가 2일 때, j는 4부터 18까지 변하며, dp [j]는 dp [j]와 dp [j-4] + 1 중 작은 값으로 갱신됩니다. 

 

이때, dp [j-4] + 1은 j를 이전에 계산한 제곱수와 2의 제곱으로 표현했을 때의 제곱수의 개수를 나타냅니다.

i가 3일 때, j는 9부터 18까지 변하며, dp [j]는 dp [j]와 dp [j-9] + 1 중 작은 값으로 갱신됩니다.

i가 4일 때, j는 16부터 18까지 변하며, dp [j]는 dp [j]와 dp [j-16] + 1 중 작은 값으로 갱신됩니다.

이렇게 모든 i, j에 대해 계산을 마치면, dp [18]은 18을 표현하는데 필요한 최소 제곱수의 개수를 나타내게 됩니다. 

🔶문제 풀이 - 많은 조건분기 이용

# 입력값 n을 받습니다.
n=int(input())

# n이 4의 거듭제곱으로 나누어 떨어지는 경우, n을 4로 계속 나눕니다. 이렇게 하면 n을 줄일 수 있습니다.
while n%4==0:
    n/=4
    
# n이 8k+7 형태의 수인 경우, 라그랑주의 네 제곱수 정리에 따라 4개의 제곱수로 표현됩니다.
if n%8==7:
    print(4)
else:
    # n이 제곱수인지 확인합니다. 제곱수인 경우 1개의 제곱수로 표현할 수 있습니다.
    for i in range(1,int(n**0.5)+1):
        if i*i==n:
            print(1)
            break
    else:
        # n이 두 개의 제곱수의 합으로 표현될 수 있는지 확인합니다.
        for i in range(int(n**0.5)+1):
            j=int((n-i*i)**0.5)
            if i*i+j*j==n:
                print(2)
                break
        else:
            # 위의 모든 경우가 아니라면 n은 세 개의 제곱수의 합으로 표현됩니다.
            print(3)

🔶문제 이해하기

n이 25라고 가정해 보겠습니다.

 

1. n은 4로 나눠지지 않습니다.

 

2. 25는 5의 제곱수이므로 첫 번째 for문을 수행합니다.

 

3. 출력값으로 1을 출력하고 반복문을 탈출합니다.

 

n이 26이라고 가정해 보겠습니다.

 

1. n은 4로 나눠지므로 n은 6이 됩니다.

 

2. 26은 두 개의 제곱수의 합으로 표현됩니다. 5 * 5 + 1 * 1 = 26, 두 번째 for문을 수행합니다.

 

3. 출력값으로 2를 출력하고 반복문을 탈출합니다.

 

n이 34567이라고 가정해 보겠습니다.

 

1. n은 4로 나눠지지 않습니다.

 

2. n이 8K+7의 형태의 수 이므로 4개의 제곱수로 표현됩니다.

 

3. 4를 출력합니다.

 

🤗파이팅입니다~ 여러분!!🤗