파이썬으로 처음 N개 자연수 제곱의 합이 X 이하가 되는 최대 N 구하기

정수 X가 주어졌을 때, 처음 N개의 자연수 제곱의 합(1² + 2² + ... + N²)이 X를 초과하지 않는 최대값 N을 구하는 문제를 살펴보겠습니다.

예를 들어 입력이 X = 7이라면 출력은 2가 됩니다. N = 3일 경우 수열의 합이 1² + 2² + 3² = 1 + 4 + 9 = 14로 X = 7을 초과하기 때문입니다. 따라서 조건을 만족하는 N의 최댓값은 2입니다.

해결 접근 방식

이 문제는 이진 탐색(Binary Search)을 활용하면 효율적으로 해결할 수 있습니다. N이 커질수록 제곱의 합도 단조 증가하기 때문에, 특정 값이 조건을 만족하는지 확인하며 탐색 범위를 절반씩 줄여나갈 수 있습니다.

알고리즘 단계

• 제곱의 합을 계산하는 함수 sum_of_squares()를 정의합니다. 이 함수는 N을 매개변수로 받습니다.

• 공식 res = (N × (N + 1) × (2 × N + 1)) / 6을 사용해 1부터 N까지 제곱의 합을 계산한 뒤 반환합니다.

• 메인 함수에서 다음 과정을 수행합니다:

  • low = 1, high = 100000, N = 0으로 초기화합니다.

  • low <= high인 동안 반복합니다.

  • mid = (low + high) // 2를 계산합니다.

  • 만약 sum_of_squares(mid) <= X라면, 현재 mid가 유효한 후보이므로 N = mid로 저장하고 low = mid + 1로 탐색 범위를 오른쪽으로 좁힙니다.

  • 그렇지 않다면 합이 X를 초과하는 것이므로 high = mid - 1로 탐색 범위를 왼쪽으로 좁힙니다.

• 반복이 끝나면 N을 반환합니다.

구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

def sum_of_squares(N):
    res = (N * (N + 1) * (2 * N + 1)) // 6
    return res

def get_max(X):
    low, high = 1, 100000
    N = 0
    while low <= high:
        mid = (high + low) // 2
        if sum_of_squares(mid) <= X:
            N = mid
            low = mid + 1
        else:
            high = mid - 1
    return N

X = 7
print(get_max(X))

실행 결과

입력:

7

출력:

2

복잡도 분석

탐색 범위가 매번 절반으로 줄어들기 때문에 시간 복잡도는 O(log N)입니다. 각 단계에서 제곱의 합을 상수 시간(O(1))에 계산할 수 있는 공식을 사용하므로 전체 성능이 매우 효율적입니다. 만약 이진 탐색 없이 1부터 차례대로 더해간다면 O(√X) 시간이 걸릴 수 있지만, 위 방법은 훨씬 빠르게 답을 찾을 수 있습니다.