C++로 수열 1, 2, 11, 12, 21…의 N번째 항 구하기

문제 소개

이 문제에서는 하나의 숫자 N이 주어지며, C++을 사용해 수열 1, 2, 11, 12, 21…의 N번째 항을 구하는 프로그램을 작성하는 것이 목표입니다.

문제 설명

다음 수열의 N번째 항을 찾아야 합니다.

1, 2, 11, 12, 21, 22, 111, 112, ... (총 N개의 항)

이를 위해서는 먼저 수열의 일반항을 도출해야 합니다.

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

입력

N = 8

출력

112

풀이 접근 방법

일반항을 유도하려면 수열을 면밀히 관찰해야 합니다. 이 수열의 값에는 오직 1과 2만 사용되며, 모든 항이 1과 2가 번갈아 배치된 형태임을 알 수 있습니다.

즉, 각 항은 이전 단계의 항에 10을 곱한 뒤 마지막 자리에 1 또는 2를 더하는 방식으로 만들어집니다. 따라서 일반항은 다음과 같습니다.

• N이 홀수인 경우: T(N) = T(N/2) × 10 + 1
• N이 짝수인 경우: T(N) = T((N/2) − 1) × 10 + 2

기저 조건은 T(1) = 1, T(2) = 2입니다. 이 재귀 관계를 이용하면 원하는 N번째 항을 쉽게 계산할 수 있습니다.

예제 코드

#include <iostream>
using namespace std;

int findNTerm(int N) {
    if(N == 1)
        return 1;
    if(N == 2)
        return 2;
    int value;
    if(N % 2 == 0){
        value = (findNTerm((N/2)-1) * 10) + 2;
    }
    else
        value = (findNTerm((N/2)) * 10) + 1;
    return value;
}

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

출력 결과

12번째 항의 값은 212

코드 설명

위 코드는 재귀 함수 findNTerm()을 사용하여 N번째 항을 계산합니다. N이 1이면 1을, 2이면 2를 반환하는 기저 조건을 설정하고, 그 외의 경우에는 N의 홀짝 여부에 따라 재귀 호출을 반복합니다.

재귀 호출이 진행될 때마다 탐색 범위가 절반으로 줄어들기 때문에 이 알고리즘의 시간 복잡도는 O(log N)으로 매우 효율적입니다.