C++에서 주어진 숫자가 2~32진법의 지정된 자릿수로 표현 가능한지 확인하는 방법

문제 개요

숫자 n과 자릿수 d가 주어졌을 때, n이 2부터 32까지의 임의의 진법에서 d자리 숫자로 표현될 수 있는지 확인하는 것이 목표입니다.

예를 들어 n = 8, d = 4라고 가정해 보겠습니다. 8은 이진법(2진수)에서 1000으로 표현되며 자릿수가 정확히 4이므로 조건을 만족합니다.

접근 방법

핵심 아이디어는 2부터 32까지의 모든 진법을 하나씩 검사하는 것입니다. 각 진법에 대해 다음 규칙으로 판단할 수 있습니다.

• 성공 조건: 숫자가 해당 진법보다 작고 남은 자릿수가 1이면 true를 반환합니다.
• 재귀 단계: 자릿수가 1보다 크고 숫자가 진법보다 크거나 같으면, num / base 연산으로 마지막 자릿수를 제거하고 자릿수를 하나 줄인 뒤 재귀적으로 다시 검사합니다.
• 실패 조건: 위 두 경우에 해당하지 않으면 false를 반환합니다.

예제 코드

#include <iostream>
using namespace std;

bool isRepresentedInDDigits(int num, int d, int base) {
    if (d == 1 && num < base)
        return true;
    if (d > 1 && num >= base)
        return isRepresentedInDDigits(num / base, --d, base);
    return false;
}

bool checkNumber(int num, int d) {
    // 2부터 32까지 모든 진법을 하나씩 검사
    for (int base = 2; base <= 32; base++)
        if (isRepresentedInDDigits(num, d, base))
            return true;
    return false;
}

int main() {
    int num = 8;
    int dig = 2;
    if (checkNumber(num, dig))
        cout << "표현할 수 있습니다";
    else
        cout << "표현할 수 없습니다";
}

출력 결과

표현할 수 있습니다

동작 과정 분석

num = 8, d = 2일 때 3진법(base = 3)에서 조건이 만족됩니다. 실행 흐름은 다음과 같습니다.

1. 첫 번째 호출: d = 2 > 1이고 num = 8 >= 3이므로, num / base = 2로 만들고 d를 1 감소시킨 상태로 재귀 호출합니다.
2. 두 번째 호출: d = 1이고 num = 2 < 3이므로 true를 반환합니다.

실제로 8을 3진수로 나타내면 22(2 × 3 + 2 = 8)로 두 자리 숫자이므로 결과가 올바릅니다.

시간 복잡도

각 진법에서의 검사는 숫자를 계속 나누는 방식이므로 O(log n)번의 재귀 호출이 발생하고, 검사 대상 진법은 최대 31개(2~32)이므로 전체 시간 복잡도는 O(log n) 수준으로 매우 효율적입니다.