[level 2] 유사 칸토어 비트열

문제 링크

성능 요약

메모리: 4.14 MB, 시간: 0.03 ms

문제 설명

수학에서 칸토어 집합은 0과 1 사이의 실수로 이루어진 집합으로, [0, 1]부터 시작하여 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만들어집니다.

남아는 칸토어 집합을 조금 변형하여 유사 칸토어 비트열을 만들었습니다. 유사 칸토어 비트열은 다음과 같이 정의됩니다.

• 0 번째 유사 칸토어 비트열은 "1" 입니다.
• n(1 ≤ n) 번째 유사 칸토어 비트열은 n - 1 번째 유사 칸토어 비트열에서의 1을 11011로 치환하고 0을 00000로 치환하여 만듭니다.

남아는 n 번째 유사 칸토어 비트열에서 특정 구간 내의 1의 개수가 몇 개인지 궁금해졌습니다.
n과 1의 개수가 몇 개인지 알고 싶은 구간을 나타내는 l, r이 주어졌을 때 그 구간 내의 1의 개수를 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ n ≤ 20
• 1 ≤ l, r ≤ 5ⁿ
  • l ≤ r < l + 10,000,000
  • l과 r은 비트열에서의 인덱스(1-base)이며 폐구간 [l, r]을 나타냅니다.

---

입출력 예

n	l	r	result
2	4	17	8

---

입출력 예 설명

2 번째 유사 칸토어 비트열은 "1101111011000001101111011" 입니다. 음영 표시된 부분은 폐구간 [4, 17] 이며 구간 내의 1은 8개 있습니다.

 

코드

#include <string>
#include <vector>
#include <cmath>
using namespace std;

int answer = 0;

void Divide(int n, long long l, long long r)
{
    long long range = 1LL * pow(5,n-1);
    int s = l/range, e = r/range;
    if(n==1)
    {
        for(int i=l;i<=r;i++) if(i!=2) answer++;
        return ;
    }
    for(int i=s+1;i<e;i++) if(i!=2) answer += (int)pow(4,n-1);
    if (s == e) Divide(n-1, l - range*s, r - range*e);
    else
    {
        if(s!=2) Divide(n-1, l - range*s, range-1);
        if(e!=2) Divide(n-1, 0,r - range*e);
    }
}

int solution(int n, long long l, long long r)
{
    Divide(n,--l,--r);
    return answer;
}

테스트 결과