수열 5, 2, 19, 13, 41…의 n번째 항을 구하는 C++ 프로그램

이 문제에서는 정수 N이 주어지며, 수열 5, 2, 19, 13, 41, 31, 71, 57…의 N번째 항을 구하는 프로그램을 작성하는 것이 목표입니다.

예제를 통한 문제 이해

입력

N = 5

출력

41

설명

주어진 수열은 5, 2, 19, 13, 41, … 로 이어지며, 이 중 5번째 항은 41입니다.

해결 접근 방법

이 문제를 푸는 가장 간단한 방법은 수열의 n번째 항에 대한 일반 공식을 활용하는 것입니다. 이 수열은 N이 짝수일 때와 홀수일 때 서로 다른 공식을 따른다는 특징이 있습니다.

N번째 항은 다음과 같이 정의할 수 있습니다.

N번째 항 = (N-1)^2 + N   (N이 짝수인 경우, N % 2 == 0)
N번째 항 = (N+1)^2 + N   (N이 홀수인 경우, N % 2 != 0)

예를 들어 N = 5(홀수)라면 (5+1)² + 5 = 36 + 5 = 41로, 실제 수열의 5번째 값과 일치함을 확인할 수 있습니다.

C++ 구현 예제

#include <iostream>
using namespace std;

int calcNthTerm(int N) {
    if (N % 2 == 0)
        return ((N - 1) * (N - 1)) + N;
    return ((N + 1) * (N + 1)) + N;
}

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

실행 결과

7번째 항은 71

코드 설명 및 복잡도

calcNthTerm() 함수는 N을 2로 나눈 나머지를 검사해 짝수와 홀수를 판별한 뒤, 해당하는 공식에 값을 대입하여 결과를 반환합니다. 단순한 조건문과 사칙연산만으로 답을 구하므로 시간 복잡도는 O(1), 추가 메모리 사용량 역시 O(1)로 매우 효율적입니다.