문제

수학에서 칸토어 집합은 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^n$
  • l ≤ r < l + 10,000,000
  • l과 r은 비트열에서의 인덱스(1-base)이며 폐구간 [l, r]을 나타냅니다.

풀이

아이디어

• n번째 '유사 칸토어 비트열'은 다음과 같이 생겼다.

(n-1번째 비트열)(n-1번째 비트열)(0이 5^(n-1)만큼 있음)(n-1번째 비트열)(n-1번째 비트열)

• 저렇게 5개의 섹터로 나눌 수 있고, 하나의 섹터 당 길이가 $5^{n-1}$이다.
• 또한, 하나의 섹터 당 1의 개수는 $4^{n-1}$개 있다.
• 이러한 구조를 이용해서, 다음과 같이 코드를 작성할 수 있다.
• [l, r] 사이의 1의 개수를 구하라는 것은 (r까지의 1의 개수) - (l-1까지의 1의 개수) 하라는 것이다.
• 이때, 2번 섹터는 모두 0으로 가득 차 있으므로, 이 점을 고려하여 코드를 작성하였다.

코드

#n에 해당하는 비트열에 대해 k번째 수까지의 1의 개수를 리턴
def f(n, k):
    if n==1:
        return k if k <= 2 else k-1

    sector_length = 5**(n-1)
    sector_ones = 4**(n-1)
    
    section = k // sector_length
    if k % sector_length == 0:
        section -= 1
    
    if section < 2:
        return sector_ones * section + f(n-1, k - sector_length * section)
    elif section == 2:
        return sector_ones * section
    else:
        return sector_ones * (section-1) + f(n-1, k - sector_length * section)
        
def solution(n, l, r):
    return f(n, r) - f(n, l-1)