문제

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

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52.

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.

출력

출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

풀이

요즘 다이나믹 프로그래밍 문제 연습중이라, 다이나믹 프로그래밍으로 분류된 문제에서 선택해서 풀고 있었는데, 점화식스러운 풀이에 너무 집착하다가 시간 초과 당하고 계속 못풀었다ㅠㅠ 알고보니 그냥 3중 for문 이용해서 브루트포스로 풀면 간단히 해결되는 문제였다. 문제 분류를 먼저 확인한 게 사고를 한정 지어 오히려 안 좋은 영향을 주기도 하는 것 같다.

• 28776KB / 76ms

def FourSquares(x):
    result = 4

    # 아래 모든 for문에서, 절반의 루트값 이하까지 보면 그 다음 for문에서 중복되므로,
    # root(해당 값) 부터 root(해당 값//2) 까지만 확인하면 된다.
    for i in range(int(n**0.5), int((n//2)**0.5)-1, -1):
        a = n - i*i
        if a == 0: return 1

        for j in range(int(a**0.5), int((a//2)**0.5)-1, -1):
            b = a - j*j
            if b == 0:
                result = min(result, 2)
                break

            for k in range(int(b**0.5), int((b//2)**0.5)-1, -1):
                c = b - k*k         
                if c == 0:
                    result = min(result, 3)
                    break

    return result


n = int(input())
print(FourSquares(n))