C++로 n번째 항이 n² − (n−1)²인 수열의 합 구하기

이 문제에서는 하나의 정수 N이 주어지며, n번째 항이 n² − (n−1)²로 정의되는 수열의 첫 n항까지의 합을 구하는 것이 목표입니다.

예시를 통해 문제를 살펴보겠습니다.

입력 : N = 3
출력 : 9

풀이 설명 —

[12 − (0)2] + [22 − (1)2] + [32 − (2)2] = 1 − 0 + 4 − 1 + 9 − 4 = 9

해결 접근 방법

이 문제는 수열의 일반항을 먼저 구한 뒤, 그 합을 공식으로 계산하는 것이 가장 효율적입니다. 일반항 기반의 공식을 활용하면 반복문 없이 O(1) 시간 복잡도로 답을 구할 수 있습니다. 또한 n이 커지면 결과값도 매우 거대해지므로, 오버플로를 방지하기 위해 모듈러 연산을 함께 적용해야 합니다.

먼저 수열의 n번째 항을 유도해 보겠습니다.

T_n = n² − (n−1)²

곱셈 공식 a² − b² = (a + b)(a − b)를 적용하면,

T_n = (n + (n−1)) × (n − (n−1))

= (2n − 1) × 1

= 2n − 1

즉, 이 수열은 1, 3, 5, 7, … 처럼 연속된 홀수로 이루어진 수열임을 알 수 있습니다. 이 일반항을 이용해 n항까지의 합을 구하면 다음과 같습니다.

sum = Σ(2k − 1)

sum = 2·Σk − Σ1

sum = 2·(n(n + 1) / 2) − n

sum = n(n + 1) − n = n² + n − n = n²

따라서 이 수열의 합은 n²입니다. 결과가 매우 큰 값이 될 수 있으므로, 최종 답은 10⁹ + 7로 나눈 나머지를 출력합니다.

예제 코드

위에서 설명한 해결 방법의 동작을 보여주는 C++ 프로그램입니다.

#include<iostream>
using namespace std;
#define mod 1000000007
long long calcSumNTerms(long long n) {
    return ((n % mod) * (n % mod)) % mod;
}
int main() {
    long long n = 4325353;
    cout << "n항까지의 수열의 합: " << calcSumNTerms(n);
    return 0;
}

출력 결과

n항까지의 수열의 합: 678443653

복잡도 분석

시간 복잡도: O(1) — 곱셈과 모듈러 연산만으로 결과를 바로 계산합니다.
공간 복잡도: O(1) — 추가적인 메모리를 사용하지 않습니다.