[programmers] 유사 칸토어 비트열

https://school.programmers.co.kr/learn/courses/30/lessons/148652

프로그래머스

 

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

작은 부분문제로 나누어 풀어야 한다.

bit[n] = bit[n-1] bit[n-1] 0...0 bit[n-1] bit[n-1]

이런 규칙이 존재한다.

따라서 n번째를 n-1번째로 쪼개서 풀었다.

또한, bit[n]의 전체 1의 개수는 4^n이므로 이 사실도 이용한다.

 

---------------------------------------------------풀이----------------------------------------------------

 

bit[n]을 위 공식에 따라 다섯 부분으로 나누어 재귀 호출을 한다.

unit은 이 다섯 부분으로 나누어진 각각의 크기를 의미하며, 5^(n-1)이다.

 

bit[n]의 l과 r이 이 다섯 부분 중 어떤 부분에 속하는지 체크(s_idx, e_idx)하고,

l이 속한 부분과 r이 속한 부분을 제외하고 가운데 부분들을 따로 구해준다.

최종적으로 (l이 속한 부분) + (가운데 부분) + (r이 속한 부분) 으로 재귀함수를 호출해 구해진다.

가운데 부분들은 각 unit 단위의 모든 1을 포함하므로, 다시말해, bit[n-1]의 모든 1을 포함하므로,

함수에서 다시 호출됐을 때, 4^n을 리턴하게 된다.

#include <string>
#include <vector>
#include <math.h>
#include <iostream>

using namespace std;

// 재귀함수
int calc_ones(int n, long long l, long long r){
    // bit[n] = bit[n-1] bit[n-1] 0*5^(n-1) bit[n-1] bit[n-1]
    //          5^(n-1)  5^(n-1)  5^(n-1)   5^(n-1)  5^(n-1)
    // bit[k]에 포함된 1의 개수 = 4^k
    int ans = 0;
    if(n == 0){
        return 1;
    }
    long long unit = pow(5, n-1);
    if(l == 0 && r == unit*5-1){
        return pow(4, n);
    }
    // 5부분으로 나누어 계산
    long long s = 0, e = unit-1;
    int s_idx = 0, e_idx = 0;   // 다섯개 중 어디 부분에 속하는가
    for(long long i = 0; i < 5; i++){
        if(s <= l && l <= e){
            s_idx = i;
        }
        if(s <= r && r <= e){
            e_idx = i;
        }
        s += unit; e += unit;
    }
    // s가 포함된 부분 따로, e가 포함된 부분 따로 호출(partial 이므로)
    if(s_idx == e_idx){
        // s와 e가 같은 부분에 포함되어 있으면, l부터 r까지로 호출
        if(s_idx != 2){
            // 0으로만 이루어진 부분이 아닐 경우에만 호출
            ans += calc_ones(n-1, l-unit*s_idx, r-unit*e_idx);
        }
    }
    else{
        // l ~ 이 묶음의 끝까지
        if(s_idx != 2){
            ans += calc_ones(n-1, l-unit*s_idx, unit-1);
        }
        // 0 ~ r까지
        if(e_idx != 2){
            ans += calc_ones(n-1, 0, r-unit*e_idx);
        }
    }
    // 완전한 한 묶음 단위
    for(int i = s_idx+1; i < e_idx; i++){
        // 0으로만 이루어진 부분은 패스
        if(i == 2){
            continue;
        }
        ans += calc_ones(n-1, 0, unit-1);
    }
    return ans;
}

// 칸토어 집합 : [0,1]에서 시작해 각 구간을 3등분하여 가운데 구간을 제외하는 방식
// 유사 칸토어 비트열 -> 0번째=1
// n번째=n-1번째 유사 칸토어 비트열에서 1을 11011로 치환, 0을 00000로 치환.
// n번째 유사 칸토어 비트열에서 특정 구간[l,r] 내의 1의 개수=?
int solution(int n, long long l, long long r) {
    int answer = 0;
    // bit[1] = 11011 => len = 5
    // 1: 4개
    // bit[2] = 11011 11011 00000 11011 11011
    //        = bit[1] bit[1] 0*5^1 bit[1] bit[1] => len = 5*5
    // 1: 4*4
    // bit[3] = bit[2] bit[2] 0*5^2 bit[2] bit[2] => len = 5*5*5
    // 1: 4*4*4
    // bit[4] = bit[3] bit[3] 0*5^3 bit[3] bit[3] => len = 5^4
    answer = calc_ones(n, l-1, r-1);
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

처음에 손으로 쓰지 않고 주석으로만 풀려고 했더니

5부분으로 나누어 계산하는 과정에서 재귀호출을 할 때 숫자를 계속 잘못 써서 오류가 났다.

앞으로는 처음부터 손으로 제대로 작성하든, 주석에 제대로 다 적어놓고 공식만 가져다 쓰든

처음부터 꼼꼼히 계획하는 습관이 필요할 것 같다.