프로그래머스 유사 칸토어 비트열 풀이: 재귀 구간 분할

유사 칸토어 비트열 문제는 전체 문자열을 실제로 만들지 않고, 5등분 구조를 따라 필요한 구간만 재귀로 내려가며 1의 개수를 세는 방식으로 풀 수 있습니다.

가운데 세 번째 구간은 항상 0이 되는 구조라서, l부터 r까지의 범위가 어느 5등분 구간에 걸치는지만 계산하면 불필요한 문자열 생성과 순회를 피할 수 있습니다.

 

핵심 정리

핵심은 n단계 비트열의 길이와 1의 개수를 미리 알아두는 것입니다. 길이는 단계마다 5배가 되고, 1의 개수는 가운데 구간을 제외하므로 4배가 됩니다. 현재 범위가 한 구간 안에 있으면 그 하위 단계로 그대로 내려가고, 여러 구간에 걸치면 왼쪽 끝, 오른쪽 끝, 중간의 완전한 구간을 나누어 더합니다. 중간 구간 중 세 번째는 0 구간이므로 합산하지 않습니다.

• 전체 비트열을 문자열로 만들면 길이가 급격히 커져 비효율적입니다.
• 각 단계는 이전 단계 5개 구간으로 나뉩니다.
• 세 번째 구간은 0으로 취급해 재귀 탐색에서 제외합니다.
• length 배열은 단계별 전체 길이를 저장합니다.
• val 배열은 단계별 1의 개수를 저장합니다.
• 범위가 여러 구간에 걸치면 왼쪽, 중간, 오른쪽을 나눠 계산합니다.

원문은 코드가 바로 시작되어 구간 분할 의도가 늦게 보였습니다. 이번 보강은 5등분 구조와 세 번째 구간 제외 규칙을 먼저 설명해, 아래 재귀 코드의 변수들이 어떤 역할인지 따라가기 쉽게 했습니다.

으허.. 머리에 쥐나긴했는데.. chatGPT한테 힌트 받고 스스로 풀긴했다 ㄷ

재귀를 통해서 하는건데.. 알아두면 두고두고 써먹을거 같긴하다.

 

#include <bits/stdc++.h>
using namespace std;

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

typedef long long ll;

ll length[21];
ll val[21];//val[3]이면 F(3)일때 1의 개수

ll solution_sub(int n, ll l, ll r) {
    if (n <= 0) return 1;
    ll answer = 0;
    if (n == 1) {
        for (int i = l; i <= r; i++) {
            if (i != 3) answer += 1;
        }
        return answer;
    }

    //n에 대해서 5등분 해서 재귀로 들어가면 되지 않을까?
    ll lx = (l - 1) / length[n - 1] + 1;
    ll rx = (r - 1) / length[n - 1] + 1;

    ll nl = l - length[n - 1] * ((l - 1) / length[n - 1]);
    ll nr = r - length[n - 1] * ((r - 1) / length[n - 1]);


    if (lx == rx) {
        if(lx!=3) answer += solution_sub(n - 1, nl, nr);
    } else {
        //왼쪽

        //answer += solution_sub(n - 1, l - length[n-1]*((l-1)/length[n-1]), r - length[n - 1] * ((r - 1) / length[n - 1]));
        ll nl = l - length[n - 1] * ((l - 1) / length[n - 1]);
        ll nr = r - length[n - 1] * ((r - 1) / length[n - 1]);
        ll a = ((l - 1) / length[n - 1] + 1) * length[n - 1];
        ll rv = nr; if (r > a) rv = length[n - 1];
        if(lx!=3) answer += solution_sub(n - 1, nl, rv);

        //오른쪽
        a = ((r - 1) / length[n - 1]) * length[n - 1];
        ll lv = nl; if (l < a) lv = 1;
        if(rx!=3) answer += solution_sub(n - 1, lv, nr);

        //중간
        for (int i = lx + 1; i < rx; i++) {
            if (i != 3) answer += val[n - 1];
        }

    }
    return answer;
}


ll solution(int n, ll l, ll r) {
    length[1] = 5; for (int i = 2; i <= 21; i++) length[i] = length[i - 1] * 5;
    val[1] = 4; for (int i = 2; i <= 21; i++) val[i] = val[i - 1] * 4;

    return solution_sub(n, l, r);
}

int main() {
    cout << solution(3, 35, 102) << endl;
    // 예시 입력: n = 2, l = 4, r = 17 → 결과는 8이어야 함
    cout << solution(2, 4, 17) << endl;

    return 0;
}

초기구현.. 거의 한번에 AC받긴함