[Beakjoon] #17626 - Four Squares

꽤 오랜 시간을 고민했는데 이해가 되지 않았던 문제이다 ... 기억하기 위해 기록함 !

 

⭐️ 문제에서 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 했다. 즉 답은 1, 2, 3, 4 네개 중 하나이다. 

⭐️ 자연수가 1개의 제곱수로 표현될 수 있는 조건에 대해 먼저 확인한 후 2, 3, 4 조건을 순서대로 확인해준다. 

조건	개수
n의 제곱근이 정수일 때	1
정수 i에 대해 n - (i^2)의 제곱근이 정수인 경우	2
정수 i, j에 대해 n - (i^2) - (j^2)의 제곱근이 정수인 경우	3
위의 어떠한 조건에도 해당하지 않는 경우	4

def sol(n):
    if int(n ** 0.5) == n ** 0.5:
        return 1
    for i in range(1, int(n ** 0.5) + 1):
        if int((n - i ** 2) ** 0.5) == (n - i ** 2) ** 0.5:
            return 2
    for i in range(1, int(n ** 0.5) + 1):
        for j in range(1, int((n - 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

if __name__ == "__main__":
    n = int(input())
    print(sol(n))

 

참고

https://simsim231.tistory.com/160