파이썬(Python)으로 n번째 항이 n² − (n−1)²인 수열의 합 구하기

이 글에서는 아래와 같은 문제 상황에 대한 해결 방법을 알아보겠습니다.

문제 정의

정수 n이 입력으로 주어졌을 때, 다음과 같이 정의되는 n번째 항을 가지는 수열의 첫 번째 항부터 n번째 항까지의 전체 합을 구해야 합니다.

Tn = n² − (n−1)²

접근 방식

n번째 항을 하나씩 계산하여 더하는 직접적인 공식은 제곱 연산과 곱셈이 반복되기 때문에 시간 복잡도가 커질 수 있습니다. 이를 줄이기 위해 여기서는 모듈러 곱셈(modular multiplication) 기법을 활용합니다.

먼저 수열의 성질을 살펴보면, 각 항은 다음과 같이 전개됩니다.

Tn = n² − (n−1)² = n² − (n² − 2n + 1) = 2n − 1

즉, 이 수열은 1, 3, 5, … 과 같은 홀수 수열이며, 앞에서부터 k개의 항을 모두 더하면 중간 항들이 서로 상쇄되어(telescoping) 결과적으로 k²가 됩니다. 따라서 n번째 항까지의 합은 단순히 n²와 같습니다.

다만 n이 매우 큰 경우 n² 값이 감당하기 어렵게 커질 수 있으므로, 오버플로를 방지하고자 일반적으로 큰 소수인 10⁹+7로 나눈 나머지를 계산합니다.

구현 예제

이제 실제 파이썬 코드를 살펴보겠습니다.

# 주어진 수열의 합을 구하는 Python 프로그램
mod = 1000000007

def findSum(n):
    return ((n % mod) * (n % mod)) % mod

# main()
n = 229137999
print(findSum(n))

출력 결과

218194447

코드 설명

• mod = 1000000007: 결과값이 너무 커지는 것을 막기 위한 모듈러 상수입니다.
• findSum(n): 수열의 합이 n²임을 이용해, n을 먼저 mod로 나눈 나머지끼리 곱한 뒤 다시 한번 mod로 나누어 결과를 반환합니다. 이렇게 하면 곱셈 과정에서 값이 비정상적으로 커지는 것을 방지할 수 있습니다.
• 모든 변수는 전역(global) 범위에서 선언되어 사용됩니다.

결론

이 글에서는 n번째 항이 n² − (n−1)²로 주어지는 수열의 합을 구하는 방법을 살펴보았습니다. 각 항이 2n−1 형태의 홀수이고, 부분합이 n²로 깔끔하게 정리된다는 점을 활용하면 복잡한 반복 계산 없이도 모듈러 곱셈만으로 효율적으로 답을 구할 수 있습니다.