C++로 수열 3, 5, 33, 35, 53…의 N번째 항 구하기

이 글에서는 수열 3, 5, 33, 35, 53…의 N번째 항을 구하는 C++ 프로그램을 살펴보겠습니다.

문제 조건은 간단합니다. 하나의 숫자 N이 주어지면, 해당 위치에 있는 수열의 값을 찾아 출력하면 됩니다.

수열의 패턴 분석

먼저 이 수열이 어떻게 만들어지는지 규칙을 확인해 보겠습니다.

• 첫 번째 항은 3, 두 번째 항은 5입니다.
• 홀수 번째 항(i ≥ 3): 이전 항 arr[i/2]에 10을 곱한 뒤 3을 더합니다.
• 짝수 번째 항(i ≥ 4): arr[(i/2) − 1]에 10을 곱한 뒤 5를 더합니다.

즉, 이 수열은 기존 숫자 끝에 3과 5를 번갈아 붙여가며 확장되는 구조입니다. 규칙을 적용해 나열하면 다음과 같습니다.

• n = 1 → 3
• n = 2 → 5
• n = 3 → 33 (arr[1] × 10 + 3)
• n = 4 → 35 (arr[1] × 10 + 5)
• n = 5 → 53 (arr[2] × 10 + 3)
• n = 6 → 55 (arr[2] × 10 + 5)

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
// 수열의 n번째 항을 구하는 함수
int printNthElement(int n){
    int arr[n + 1];
    arr[1] = 3;
    arr[2] = 5;
    for (int i = 3; i <= n; i++) {
        if (i % 2 != 0)
            arr[i] = arr[i / 2] * 10 + 3;
        else
            arr[i] = arr[(i / 2) - 1] * 10 + 5;
    }
    return arr[n];
}
int main(){
    int n = 6;
    cout << printNthElement(n);
    return 0;
}

출력 결과

55

코드 동작 원리

위 코드는 배열을 활용해 수열의 항을 차례대로 계산합니다.

1. 배열의 1번째 요소를 3, 2번째 요소를 5로 초기화합니다.
2. 3부터 N까지 반복하면서 인덱스가 홀수이면 arr[i/2] × 10 + 3을, 짝수이면 arr[(i/2) − 1] × 10 + 5를 계산하여 저장합니다.
3. 모든 반복이 끝나면 arr[N] 값을 반환합니다.

예를 들어 n = 6일 경우, arr[6] = arr[2] × 10 + 5 = 5 × 10 + 5 = 55가 되어 위와 같은 출력이 나타납니다.

각 항은 이미 계산된 이전 값을 참조하므로 O(1) 시간에 구할 수 있으며, 전체 시간 복잡도는 O(N)입니다. 참고로 가변 길이 배열(VLA)은 C++ 표준이 아니므로, 이식성을 높이려면 vector<int>를 사용하는 것이 좋습니다.