title: "[프로그래머스] 유사 칸토어 비트열 Python 파이썬 해설 (Level 2) - 이도훈"
cleanUrl: "programmers/148652"
description: "프로그래머스 Level 2 문제 [유사 칸토어 비트열]의 풀이를 정리합니다."

문제 설명 및 제한사항

문제 설명

수학에서 칸토어 집합은 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]을 나타냅니다.

아이디어 및 해결 방법

코드

cache = {}

def solve(n, l, r):
    if (n, l, r) in cache:
        return cache[(n, l, r)]
    
    if l == 1 and r == 5**n:
        cache[(n, l, r)] = 4**n
        return 4**n
    
    ans = 0
    for i in range(5):
        # 5**(n-1) * 2 + 1 부터 5**(n-1) * 3 까지는 0 이다.
        if i == 2:
            continue
        start, end = 5**(n-1) * i + 1, 5**(n-1) * (i+1)
        
        if r < start or l > end:
            continue
        
        ans += solve(n-1, max(1, l-start+1), min(5**(n-1), r-start+1))
    
    cache[(n, l, r)] = ans
    return ans

def solution(n, l, r):
    return solve(n, l, r)

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges