C++로 3과 4만 사용하는 숫자 체계에서 n번째 숫자 구하기

이 문제에서는 하나의 수 N이 주어지며, 3과 4로만 이루어진 숫자 체계에서 N번째 숫자를 찾아야 합니다.

해당 숫자 체계는 3, 4, 33, 34, 43, 44, 333, 334, 343, 344, … 순서대로 구성됩니다.

문제 이해를 위한 예시

입력

N = 6

출력

44

설명

숫자 체계의 요소는 다음과 같습니다 — 3, 4, 33, 34, 43, 44… 여기서 6번째 숫자는 44입니다.

해결 접근 방법

이 숫자 체계는 이진수 체계와 매우 유사합니다. 단, 숫자 0은 3으로, 숫자 1은 4로 대체된 형태입니다. 편의상 이를 'sBinary'라고 부르겠습니다.

즉, N번째 숫자는 (N-1)을 sBinary 방식으로 변환한 결과와 같습니다.

이 원리를 활용하면 문제를 아주 간단하게 해결할 수 있습니다. 먼저 (N-1)에 해당하는 이진수를 구한 뒤, 그 이진수의 각 자릿수에 3을 더해주면 원하는 숫자를 얻을 수 있습니다.

십진수를 이진수로 변환하는 방법

십진수를 이진수로 변환하려면 해당 수를 2로 계속 나누면서 나머지를 기록하고, 몫이 0이 될 때까지 반복한 후 나머지들을 역순으로 읽으면 됩니다. 본 솔루션에서는 재귀 함수를 사용해 이 과정을 효율적으로 구현했습니다.

솔루션 동작을 보여주는 프로그램

예시

#include<iostream>
using namespace std;
void findNThTermNumberSystem(int N) {
    if(N == 1 || N == 2) {
        cout<<(N-1) + 3;
        return;
    }
    N -= 1;
    findNThTermNumberSystem(N/2);
    cout<<((N % 2) + 3);
}
int main(){
    int N = 12;
    cout<<N<<"th term of the number system is ";
    findNThTermNumberSystem(N);
    return 0;
}

출력

12th term of the number system is 434