[Programmers] Level 2. 유사 칸토어 비트열

🔗 Problem Link

프로그래머스

---

❔Thinking

• n-1번째의 1은 11011로, 0은 00000으로 치환한다. (0번째는 1)
• 1 <= n <= 20, 1<= l, r <= 5^n
• l과 r 구간이 주어질 때, 해당 구간의 1의 개수를 반환한다. (l과 r은 폐구간)

---

💻Solution

def solution(n, l, r):
    answer = 0
    for i in range(l-1, r):
        while True:
            if i % 5 == 2:
                break
            elif i < 5:
                answer += 1
                break
            i //= 5
    return answer

---

🗝️keypoint

1. n이 20까지이기 때문에, 5^20은 시간 내에 반복문으로 확인할 수 없다.
2. 1과 0의 위치는 일정한 규칙을 가진다. (모든 치환은 11011, 00000 이므로 5개)
   1. 인덱스가 5 이하라면, 나머지가 2인 인덱스에는 0이 위치한다.
   2. 인덱스가 5 이상이라면, 5로 나눈 몫을 생각한다.