수열 1, 4, 15, 72, 420…의 N번째 항을 구하는 C++ 프로그램

이 문제에서는 정수 N이 주어졌을 때, 수열 1, 4, 15, 72, 420…의 N번째 항을 구하는 프로그램을 작성하는 것이 목표입니다.

문제 이해하기

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

입력

N = 4

출력

72

N = 4가 입력되면 수열의 네 번째 항인 72가 출력되어야 합니다.

해결 접근 방식

가장 간단한 방법은 수열의 N번째 항에 대한 일반 공식을 찾는 것입니다. 이를 위해서는 먼저 수열의 패턴을 관찰한 뒤, 이를 일반화된 식으로 도출해야 합니다.

주어진 수열은 팩토리얼(factorial)과 어떤 계수의 곱으로 분해해 볼 수 있습니다.

1, 4, 15, 72, 420…
1!*(X1), 2!*(X2), 3!*(X3), 4!*(X4), 5!*(X5)...
1*(1), 2*(2), 6*(5/2), 24*(3), 120*(7/2)...

여기서 곱해지는 계수들의 수열은 다음과 같습니다.

1, 2, 2.5, 3, 3.5…
즉, (n+2)/2 입니다.

따라서 N번째 항의 일반 공식은 다음과 같이 정리할 수 있습니다.

T(N) = ( N! * (N + 2) ) / 2

구현 예제

위 공식을 활용한 솔루션의 동작을 보여주는 프로그램입니다.

#include <iostream>
using namespace std;

// N의 팩토리얼을 계산하는 함수
int calcFactorial(int N) {
    int factorial = 1;
    for (int i = 1; i <= N; i++) {
        factorial = factorial * i;
    }
    return factorial;
}

// 수열의 N번째 항을 계산하는 함수
int calcNthTerm(int N) {
    return (calcFactorial(N) * (N + 2) / 2);
}

int main() {
    int N = 7;
    cout << N << "번째 항의 값은 " << calcNthTerm(N);
    return 0;
}

출력 결과

7번째 항의 값은 22680

코드 설명

• calcFactorial() 함수: 반복문을 이용해 1부터 N까지의 값을 차례로 곱하여 N!을 계산합니다.
• calcNthTerm() 함수: 팩토리얼 값에 (N+2)/2를 곱하여 수열의 N번째 항을 반환합니다.
• main() 함수: N = 7로 설정한 뒤 결과를 출력합니다. 실제로 7! × (7+2) ÷ 2 = 5040 × 9 ÷ 2 = 22680으로 계산 결과와 정확히 일치합니다.

이처럼 수열의 규칙을 관찰해 일반항 공식만 찾아내면, 복잡한 반복 연산 없이도 O(N) 시간 안에 간단하게 원하는 항을 구할 수 있습니다.