[Boj/python] 17626번) Four Squares

문제 : https://www.acmicpc.net/problem/17626
난이도 : 실버3

접근 방법

• 해당 문제에서는 제곱수가 최소의 개수로 이루어져 있는 경우를 찾아야므로, n보다 작은 제곱수를 빼준 모든 경우의 최소값을 구한뒤 1을 더해주면 해결 가능하다

---

풀이

1.DP

• 1부터 n까지를 다루기 위해 n+1 크기의 배열을 생성한다.
• 어떠한 자연수 n에 대해서 n보다 작은 제곱수를 뺀다면 $(n-i^2)$, 그 수는 반드시 어떠한 제곱수들의 합일 것이므로 $(n-i^2)$를 구성하고 있는 제곱수의 개수+1로 이루어져있다고 볼 수 있다.
• 따라서 $(n-i^2)$들 중 최솟값을 찾아 +1을 하여 답을 구한다.

n=int(input())

dp=[0]*(n+1)
dp[1]=1

for i in range(2,n+1):
     mini=1e9

     for j in range(1,int(i**(0.5))+1):
         mini=min(mini,dp[i-(j**2)])
     dp[i]=mini+1
     
print(dp[n])

• python3로 제출했을 때는 시간초과가 발생했다.
  • 시간복잡도 : $Θ(𝑛√n)$

2. 브루트포스

import math
n=int(input())

dp=[0 if i**0.5%1 else 1 for i in range(n+1)]

mini=4
def square(n):
    if int(math.sqrt(n))==math.sqrt(n):
        return True
    else:
        return False

if square(n):
    mini = 1
else:
    for i in range(int(math.sqrt(n)),0,-1):
        if square(n-(i**2)):
            mini=2
            break
        else:
            for j in range(int(math.sqrt(n-i**2)),0,-1):
                if square(n-i**2-j**2):
                    mini=3
                    break

print(mini)

• 시간 복잡도
  • 완전제곱 검사: O(1)
  • 2제곱 , 3제곱 합 검사 : 최대 √n * √n = n회
    → 전체 : Θ(n)