브루트포스는 무조건 모든 경우의 수를 따진다고 다 맞지 않다 !!! (당연함)

1. 내 풀이: 실패 (시간초과)

import sys
import math
from itertools import combinations
input = sys.stdin.readline

n = int(input())

maximum = int(math.sqrt(n))
num_list = list(range(1, maximum+1))
num_list = [o**2 for o in num_list]

two = combinations(num_list, 2)
three = combinations(num_list, 3)
four = combinations(num_list, 4)

minCnt = 5
cnt = 0

for o in num_list:
    if o == n:
        cnt = 1
        minCnt = min(cnt, minCnt)
        print(minCnt)
        exit()

for tw in two:
    if sum(tw) == n:
        cnt = 2
        minCnt = min(cnt, minCnt)
        print(minCnt)
        exit()

for th in three:
    if sum(th) == n:
        cnt = 3
        minCnt = min(cnt, minCnt)
        print(minCnt)
        exit()

for f in four:
    if sum(f) == n:
        cnt = 4
        minCnt = min(cnt, minCnt)
        print(minCnt)
        exit()

조금(이 아니라 아주 많이) 무식한 방법 ... ㅎㅎ
제일 가까운 제곱수까지 리스트 만들어두고 2개씩... 3개씩... 마지막으로 4개씩 뽑은 ... 모든 수들의 경우를 다 더해보면서 하는 거다 ^^ ~~ ^^

2. 다른 풀이

import math
 
def fourSquares(n):
    # √n이 정수일 때
    if int(math.sqrt(n)) == math.sqrt(n):
        return 1
    # √(n - i^2)이 정수일 때
    for i in range(1, int(math.sqrt(n)) + 1):
        if int(math.sqrt(n - i**2)) == math.sqrt(n - i**2):
            return 2
    # √(n - i^2 - j^2)이 정수일 때
    for i in range(1, int(math.sqrt(n)) + 1):
        for j in range(1, int(math.sqrt(n - i**2)) + 1):
            if int(math.sqrt(n - i**2 - j**2)) == math.sqrt(n - i**2 - j**2):
                return 3
    # 남은 경우는 4
    return 4
 
 
n = int(input())
print(fourSquares(n))

풀이 출처: https://kau-algorithm.tistory.com/564

얘도 모든 경우를 다 따지지만 꼭 필요한 경우 (2, 3) 만 복잡하게 짜서 그나마 효율을 높인 방법 ... !

3. 마치며

브루트포스라고 무턱대고 하기보단 머리를 써서 조금이라도 더 효율적으로 짜봐야겠다.