C++로 삼각수 수열(1, 3, 6, 10…)의 합 구하기

문제 소개

숫자 n이 주어졌을 때, 삼각수(Triangular Number) 수열 1, 3, 6, 10 … 의 처음 n개 항의 합을 계산하는 프로그램을 작성하는 것이 이번 문제의 목표입니다.

합을 구하기 전에, 삼각수가 정확히 무엇인지 먼저 짚고 넘어가겠습니다.

삼각수(Triangular Number)란?

삼각수는 이름 그대로 삼각형 모양으로 배열할 수 있는 수를 말합니다. 첫 번째 행에는 점 1개, 두 번째 행에는 점 2개, 세 번째 행에는 점 3개를 놓는 식으로 아래로 내려갈수록 점을 하나씩 늘려가며 삼각형을 만들 때, 각 단계까지 쌓인 점의 총 개수가 바로 그 단계의 삼각수입니다.

C++로 삼각수 수열(1, 3, 6, 10…)의 합 구하기

예를 들어 T1 = 1, T2 = 1+2 = 3, T3 = 1+2+3 = 6, T4 = 1+2+3+4 = 10처럼 늘어나며, 일반항은 Tn = n(n+1)/2 입니다.

예제로 문제 이해하기

입력:

n = 4

출력: 20

설명: sum = T1 + T2 + T3 + T4 = 1 + 3 + 6 + 10 = 20

풀이 방법 1: 반복문으로 삼각수를 하나씩 더하기

가장 직관적인 접근 방법은 주어진 n개의 삼각수를 모두 계산한 뒤, 차례대로 합계(sum) 변수에 더해가는 것입니다.

알고리즘

합계 변수를 초기화한다: sum = 0
1단계: i = 1부터 n까지 반복하며 2~3단계를 수행한다.
2단계: 각 i에 대해 삼각수 공식 t[i] = i×(i+1)/2 를 이용해 i번째 삼각수를 계산한다.
3단계: 합계를 갱신한다: sum += t[i]
4단계: sum을 반환한다.

C++ 구현 예제

#include <iostream>
using namespace std;

int calcSeriesSum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += i * (i + 1) / 2;
    return sum;
}

int main() {
    int n = 6;
    cout << "삼각수 수열 1, 3, 6, 10 ... 의 합은 " << calcSeriesSum(n);
    return 0;
}

출력:

삼각수 수열 1, 3, 6, 10 ... 의 합은 56

이 방법은 구현이 간단하지만 반복문을 n회 실행해야 하므로 시간 복잡도가 O(n)입니다. n이 커질수록 비효율적이기 때문에, 더 나은 방법이 필요합니다.

풀이 방법 2: 수학 공식으로 한 번에 계산하기

훨씬 효율적인 방법은 삼각수 수열의 합에 대한 직접 공식을 활용하는 것입니다. Ti를 i번째 삼각수라고 하면 다음과 같습니다.

T1 = 1
T2 = 3
T3 = 6
Tn = n(n+1) / 2

전체 합을 수식으로 전개해 보면 다음과 같습니다.

sum = 1 + 3 + 6 + 10 + …
sum = T1 + T2 + T3 + … + Tn
sum = ∑ Ti  (i = 0 ~ n)
sum = ∑ n(n+1)/2
sum = ½ (∑ n² + ∑ n)
sum = ½ [ n(n+1)(2n+1)/6 + n(n+1)/2 ]
sum = ½ · n(n+1)/2 · [ (2n+1)/3 + 1 ]
sum = ¼ · n(n+1) · [ (2n+1+3)/3 ]
sum = ¼ · n(n+1) · [ (2n+4)/3 ]
sum = ¼ · n(n+1) · [ 2(n+2)/3 ]
sum = n(n+1)(n+2) / 6

따라서 삼각수 수열의 합에 대한 일반 공식은 다음과 같습니다.

합(Sum) = n × (n+1) × (n+2) / 6

이 공식을 사용하면 반복문 없이 상수 시간 O(1) 만에 결과를 얻을 수 있습니다.

C++ 구현 예제

#include <iostream>
using namespace std;

int calcSeriesSum(int n) {
    return (n * (n + 1) * (n + 2)) / 6;
}

int main() {
    int n = 6;
    cout << "삼각수 수열 1, 3, 6, 10 ... 의 합은 " << calcSeriesSum(n);
    return 0;
}

출력:

삼각수 수열 1, 3, 6, 10 ... 의 합은 56

마무리

삼각수 수열의 합은 단순 반복문으로도 충분히 구할 수 있지만, 공식 n(n+1)(n+2)/6을 활용하면 아무리 큰 n 값이라도 즉시 계산할 수 있습니다. 코딩 테스트나 면접에서는 반복문 풀이에 만족하지 말고, 수학적 패턴을 찾아 O(1) 풀이를 제시하는 것이 훨씬 좋은 인상을 남깁니다.