C++로 N번째 오각뿔수(오각형 피라미드 수) 구하기

오각뿔수란 무엇인가?

오각뿔수(Pentagonal Pyramidal Number)는 오각형을 밑면으로 하는 피라미드에 쌓을 수 있는 물체의 총 개수를 나타내는 수입니다. 즉, 첫 번째부터 N번째까지의 오각수(Pentagonal Number)를 모두 더한 값이 곧 N번째 오각뿔수가 됩니다.

오각수와 오각뿔수의 관계

오각수는 다음 공식으로 구할 수 있습니다.

(3 × n² − n) / 2

이 공식으로 구한 오각수들을 순서대로 나열하면 1, 5, 12, 22, 35, 51 ... 이 되며, 이 값들을 처음부터 N번째까지 더하면 N번째 오각뿔수를 얻을 수 있습니다.

예시

입력 : N = 4
출력 : 40
설명 : 처음 네 개의 오각수 1, 5, 12, 22의 합은 40입니다.

입력 : N = 6
출력 : 126
설명 : 처음 여섯 개의 오각수 1, 5, 12, 22, 35, 51의 합은 126입니다.

해결 방법 1: 단순 반복 접근법

가장 직관적인 방법은 1부터 N까지 차례대로 탐색하면서 각 오각수를 계산하고 누적으로 더하는 것입니다. 오각수는 앞서 소개한 공식 (3 × n² − n) / 2를 이용해 구합니다.

예를 들어 n = 2일 때, 오각수 = (3 × 2² − 2) / 2 = 5가 됩니다.

C++ 코드 예제

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N = 6, SUM = 0;

    // 1부터 N까지 순회하면서
    for (int i = 1; i <= N; i++) {
        // i번째 오각수를 계산하여 SUM에 더함
        SUM = SUM + (3 * i * i - i) / 2;
    }
    cout << "N번째 오각뿔수: " << SUM << endl;
    return 0;
}

실행 결과

N번째 오각뿔수: 126

이 방법은 이해하기 쉽지만, 1부터 N까지 모두 순회해야 하므로 시간 복잡도가 O(N)입니다.

해결 방법 2: 공식을 활용한 효율적 접근법

반복문 없이 한 번의 계산으로 답을 구할 수 있는 수학적 공식이 존재합니다. N번째 오각뿔수는 다음과 같습니다.

N² × (N + 1) / 2

이 공식을 사용하면 시간 복잡도 O(1)만에 결과를 얻을 수 있어 훨씬 효율적입니다.

C++ 코드 예제

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N = 6, result;
    // 공식을 이용해 N번째 오각뿔수를 바로 계산
    result = N * N * (N + 1) / 2;
    cout << "N번째 오각뿔수: " << result << endl;
    return 0;
}

실행 결과

N번째 오각뿔수: 126

마무리

이 글에서는 N번째 오각뿔수를 구하는 문제를 다루었습니다. 1부터 N까지 오각수를 하나씩 더하는 단순 반복 방식과, 공식 N² × (N + 1) / 2를 활용하는 효율적인 방식 두 가지를 살펴보았습니다. 소개한 코드는 C++뿐만 아니라 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 큰 N 값을 다룰 때는 O(1) 공식 기반 접근법을 사용하는 것이 좋습니다.