C++로 수열 0, 0, 2, 1, 4, 2, 6, 3, 8…의 N번째 항 구하기

이 문제에서는 하나의 숫자 N이 주어지며, 우리의 과제는 C++를 사용하여 다음 수열의 N번째 항을 찾는 프로그램을 작성하는 것입니다.

0, 0, 2, 1, 4, 2, 6, 3, 8 …

문제 설명

주어진 수열에서 N번째 항을 찾아야 합니다.

0, 0, 2, 1, 4, 2, 6, 3, 8 .... N개의 항

이를 위해서는 수열의 일반항(일반식)을 먼저 찾아야 합니다.

입력 예시

N = 8

출력 예시

3

해결 접근 방법

수열의 일반항을 찾으려면 수열을 자세히 관찰해야 합니다. 이 수열은 두 개의 수열이 섞여 있어 한눈에 패턴을 파악하기가 다소 어렵습니다. 즉, 홀수 번째 위치에 하나의 수열이, 짝수 번째 위치에 또 다른 수열이 놓여 있는 구조입니다.

홀수 번째 항의 수열: 0, 2, 4, 6, 8, 10, 12, ...

짝수 번째 항의 수열: 0, 1, 2, 3, 4, 5, 6, ...

따라서 수열의 n번째 항은 다음과 같이 정리할 수 있습니다.

• n이 홀수인 경우: 값은 (n − 1)
• n이 짝수인 경우: 값은 T_(n−1) / 2, 즉 바로 앞 항을 2로 나눈 값

예를 들어 N = 13인 경우, 13은 홀수이므로 13번째 항의 값은 13 − 1 = 12가 됩니다.

예제 코드

#include <iostream>
using namespace std;

int findNTerm(int N) {
    if (N % 2 == 0)
        return findNTerm(N - 1) / 2;   // 짝수 번째 항: 앞 항의 절반
    else
        return (N - 1);                // 홀수 번째 항: n - 1
}

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

실행 결과

13번째 항의 값은 12

코드 설명

위 코드는 재귀 함수를 활용하여 N번째 항을 계산합니다. N이 짝수이면 바로 앞 홀수 항의 값을 구한 뒤 2로 나누고, N이 홀수이면 단순히 N − 1을 반환합니다. 이러한 규칙만 파악하면 별도의 반복문 없이도 O(log N)에 가까운 효율적인 방식으로 원하는 항을 빠르게 구할 수 있습니다.