유사 칸토어 문자열

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

이렇게는 제한 시간 내에 풀 수 없다

def solution(n, l, r):
    prev = [1]
    for _ in range(n):
        temp = []
        for each in prev:
            if each == 1:
                temp.extend((1, 1, 0, 1, 1))
            else:
                temp.extend((0, 0, 0, 0, 0))
        prev = temp
    return sum(int(each) for each in prev[l - 1: r])

재귀를 이용하여 풀 수 있다. 

def solution(n, l, r):
    def solve(num):
        if num <= 5:
            return sum((1, 1, 0, 1, 1)[:num])
        digits = int(log(num, 5))
        quotient, remainder = divmod(num, 5 ** digits)
        if quotient == 2:
            return quotient * (4 ** digits)
        elif quotient > 2:
            return (quotient - 1) * (4 ** digits) + solve(remainder)
        else:
            return quotient * (4 ** digits) + solve(remainder)

    from math import log
    return solve(r) - solve(l - 1)

1
11011
1101111011000001101111011
11011110110000011011110111101111011000001101111011000000000000000000000000011011110110000011011110111101111011000001101111011

11011이 힌트.
합은 4의 제곱으로 커지고.. 
위치는 5의 제곱으로 커진다.
3/5 분위는 0..

5의 몇 제곱인지 찾기위해
밑이 5인 로그를 이용했다. 
5 ** 1 <= X < 5 ** 2 일 때 int(log(X, 5)) = 1이 된다. 

0열의 합은 4**0 = 1
1열의 합은 4**1 = 4
2열의 합은 4**2 = 16
3열의 합은 4**3 = ...

0열을 제외하고 1열, 2열, 3열을 보면 공통적으로 5등분 중 세 번째(가운데) 분위는 모두 0이다. 
1열은 1(=5**0)로 나누었을 때 몫이 2인 지점. 
2열은 5(=5**1)로 나누었을 때 몫이 2인 지점. 
3열은 뭘로 나누었을 때 몫이 2인 지점일까?
2열의 길이와 같은 5의 제곱임을 알 수 있다.

인덱스는 0에서 시작하므로
[0~24]가 5등분 중 첫 번째 분위이고 이를 25로 나누면 모두 몫은 0이다. 
[25~49]가 두 번째 분위이고 이를 25로 나누면 모두 몫은 1이다. 
[50~74]가 세 번째 분위이고 이를 25로 나누면 모두 몫은 2이다. 

3열을 기준으로 생각해 보자. 
3열의 1/5 부분의 부분합은 2열의 합(4**2)과 같다. 누적합은 2열의 합(4**2)이다. 
(실제 위치가 이 뒤여야 누적합을 사용할 수 있다는 것이 함정.)
3열의 2/5 부분의 부분합은 2열의 합(4**2)과 같다. 누적합은 2열의 합 * 2 (=4**2*2)이다. 
3열의 3/5 부분의 부분합은 0이다. 누적합은 2열의 합 * 2 (=4**2*2)이다. 
3열의 4/5 부분의 부분합은 2열의 합(4**2)과 같다. 누적합은 2열의 합 * 2 (=4**2*2)이다. 
3열의 5/5 부분의 부분합은 2열의 합(4**2)과 같다. 누적합은 3열의 합 * 3 (=4**2*3)이다. 

실제 위치를 기준으로 생각해 보자. 
5의 x제곱으로 나누어 떨어지는 부분은 위의 예처럼 쉽게 합을 구할 수 있고. 
나머지는 재귀적으로 처리할 수 있다. 
단 3/5 분위는 0으로 채워져 있으므로 remainder(나머지)를 0으로 보아야 한다.

전체적인 흐름 중심으로 쉽게 설명하려고 노력해 보았다... ㅠ,.ㅠ 

위 설명이 이해가 간다면 아래 코드도 이해가 갈 것이다. 

def solution(n, left, right):
    def solve(num):
        if num <= 5:
            return sum((1, 1, 0, 1, 1)[:num])
        digits = int(log(num, 5))
        q, r = divmod(num, 5 ** digits)
        return (q - (1 if q > 2 else 0)) * (4 ** digits) + (0 if q == 2 else solve(r))

    from math import log
    return solve(right) - solve(left - 1)

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.02ms, 10.3MB)
테스트 3 〉	통과 (0.03ms, 10.3MB)
테스트 4 〉	통과 (0.03ms, 10.3MB)
테스트 5 〉	통과 (0.03ms, 10.4MB)
테스트 6 〉	통과 (0.04ms, 10.5MB)
테스트 7 〉	통과 (0.03ms, 10.3MB)
테스트 8 〉	통과 (0.04ms, 10.4MB)
테스트 9 〉	통과 (0.04ms, 10.5MB)
테스트 10 〉	통과 (0.05ms, 10.3MB)
테스트 11 〉	통과 (0.02ms, 10.4MB)
테스트 12 〉	통과 (0.03ms, 10.3MB)
테스트 13 〉	통과 (0.03ms, 10.3MB)
테스트 14 〉	통과 (0.02ms, 10.3MB)
테스트 15 〉	통과 (0.02ms, 10.3MB)

아까 마법의 엘리베이터 문제도 그렇고..
레벨 2 문제가 왜 이렇게 어려워진 거지 ㅠ,.ㅠ