C++로 수열 1, 1, 2, 6, 24…의 N번째 항 구하기

문제 개요

이 문제에서는 정수 N이 하나 주어지며, 우리의 목표는 수열 1, 1, 2, 6, 24, …의 N번째 항을 구하는 프로그램을 작성하는 것입니다.

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

입력

N = 7

출력

720

설명

주어진 수열은 다음과 같습니다 — 1, 1, 2, 6, 24, 120, 720. 따라서 7번째 항의 값은 720입니다.

풀이 접근 방식

수열을 자세히 관찰해 보면 각 항이 팩토리얼(factorial) 값으로 구성되어 있음을 알 수 있습니다. 즉, 이 수열은 0!, 1!, 2!, 3!, 4!… 순으로 진행되는 팩토리얼 수열입니다.

따라서 N번째 항을 구하는 가장 간단한 방법은 일반항 공식을 활용하는 것입니다.

N번째 항 = (N−1)!

예를 들어 N = 7인 경우, (7−1)! = 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720이 됩니다.

이 솔루션의 동작을 보여주는 프로그램입니다.

예제 코드

#include <iostream>
using namespace std;

int calcNthTerm(int N) {
    if (N <= 1)
        return 1;
    int factorial = 1;
    for (int i = 1; i < N; i++)
        factorial *= i;
    return factorial;
}

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

실행 결과

8번째 항의 값은 5040

복잡도 분석

• 시간 복잡도: O(N) — 반복문을 통해 1부터 N−1까지 한 번씩 곱셈을 수행합니다.
• 공간 복잡도: O(1) — 추가적인 메모리 사용 없이 상수 공간만 필요합니다.

참고 사항

팩토리얼 값은 매우 빠르게 증가하기 때문에, int 자료형은 약 13!부터 오버플로우가 발생합니다. 더 큰 N을 처리하려면 long long 또는 unsigned long long 자료형을 사용하는 것이 좋습니다.