[백준] 17626번 Four Squares

💡문제접근

• 처음엔 그리디 알고리즘으로 접근해서 푸는 문제로 생각해서 도전했는데 시간 제한이 0.5초가 주어진걸 보고 그리디가 아닌 것 같다고 생각해서 결국 모든 경우를 탐색하는 브루트포스 알고리즘을 이용했다.
• 탐색 범위를 줄이기 위해 제곱근을 이용해서 탐색을 진행했다.

💡코드(메모리 : 31256KB, 시간 : 64ms)

import sys
input = sys.stdin.readline

N = int(input())

def Four_Square(X):
	# 제곱근의 경우 1을 리턴
    if int(X**0.5) == X**0.5:
        return 1
    for i in range(1, int(X**0.5)+1):
        if int((N-i**2)**0.5) == ((N-i**2)**0.5):
            return 2
    for i in range(1, int(X**0.5)+1):
        for j in range(1, int((X-i**2)**0.5)+1):
            if int((N-i**2-j**2)**0.5) == ((N-i**2-j**2)**0.5):
                return 3
    return 4

print(Four_Square(N))

💡소요시간 : 34m