[알고리즘] 유사 칸토어 비트열

개발자 김선호·2025년 8월 26일

C++알고리즘 프로그래머스

이 문제는 칸토어 집합에서 아이디어를 가져온 문자열 문제입니다.

처음 문자열은 "1" 입니다.
매 단계마다 "1"은 "11011"로, "0"은 "00000"으로 변환됩니다.
이렇게 만들어진 무한한 문자열에서, 주어진 구간 [l, r]에 포함된 '1'의 개수를 구하는 문제입니다.

예를 들어,

n=1일 때 문자열은 "11011"
n=2일 때 문자열은 "11011 11011 00000 11011 11011"

이런 식으로 5배씩 길어지면서 점점 복잡해집니다.

단순 시도와 한계

처음엔 문자열을 직접 생성해서 [l, r] 구간을 세면 될 것 같지만, 문제는 문자열 길이가 너무 크다는 데 있습니다.

n=1 → 길이 5
n=2 → 길이 25
n=3 → 길이 125
…
n=20 → 길이 5^20 (약 95조!)

문자열을 직접 만드는 건 불가능합니다. 따라서 구간만 추적하면서 계산해야 합니다.

핵심 아이디어

각 단계에서 만들어지는 문자열은 항상 5등분할 수 있습니다.

예: "11011" = [1][1][0][1][1]
1구간 = 이전 단계 문자열
2구간 = 이전 단계 문자열
3구간 = 전부 0
4구간 = 이전 단계 문자열
5구간 = 이전 단계 문자열

즉, 전체 문자열을 직접 만들 필요 없이

우리가 원하는 구간이 어느 블록에 속하는지 확인하고
블록이 전부 0이면 건너뛰고
블록이 1을 유지하는 구간이면 다시 (n-1) 단계로 내려가 계산

이런 재귀 분할 정복 방식으로 해결할 수 있습니다.

예를 들어, n = 3일 때는 길이 125의 비트열이 만들어지는데, 5등분으로 잘랐을 때 하나의 파트는 n = 2(길이 25의 비트열)과 동일합니다. 그렇다면 n = 2인 비트열을 다시 5등분으로 잘랐을 때 하나의 파트는 n = 1일 때와 동일할 것입니다. 이를 계속 반복하는 것이죠. (단, 가운데 파트는 0으로만 이루어져 있으므로 제외)

소스코드

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>
#include <cmath>

using namespace std;

// n = 20일 때 길이는 5 ^ 20 이기 때문에 단순 문자열대입으로는 불가능

long long countOnes(int n, long long l, long long r) 
{
    if (n == 0) return 1;

    long long len = 1;
    for (int i = 0; i < n; i++) len *= 5; 
    long long part = len / 5;             

    long long ans = 0;
    for (int i = 0; i < 5; i++) 
    {
        long long start = part * i + 1;
        long long end   = part * (i + 1);

        if (r < start || l > end) continue;

        if (i == 2) 
        {
            continue;
        } 
        else 
        {
            ans += countOnes(n - 1,
                             max(l, start) - start + 1,
                             min(r, end)   - start + 1);
        }
    }
    return ans;
}

int solution(int n, long long l, long long r) {
    return countOnes(n, l, r);
}

비슷한 문제와 아이디어

예를 들어 1000 x 1000 크기의 2차원 평면이 있다고 가정해봅시다. 이 월드 안에서 특정 오브젝트의 위치를 찾으려면 어떻게 할까요? 가장 단순한 방법은 위에서부터 한 칸씩 차례대로 확인하는 것입니다.

첫 번째 칸을 확인 → 원하는 오브젝트가 없으면 다음 칸
두 번째 칸을 확인 → 없으면 또 다음 칸
… 이런 식으로 전부 확인

최악의 경우 1000 × 1000 = 1,000,000번 확인해야 원하는 위치를 알아낼 수 있습니다.
작은 예제에서는 문제가 없을 수 있지만, 맵 크기가 커지면 탐색 비용은 기하급수적으로 늘어나게 됩니다. 마치 위의 문제를 직접 문자열을 대입해서 푸는 것 처럼 말입니다.