[프로그래머스] 유사 칸토어 비트열 - C++

문제 설명

수학에서 칸토어 집합은 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 함수를 완성해주세요.

---

 

n 번째 칸토어 비트열은 (n - 1) (n - 1) 00000 (n - 1) (n - 1)로 이루어져 있다.

이는 n번째 비트열은 5등분을 할 수 있다는 것이다. 분할정복으로 풀어야겠다는 생각을 할 수 있다. 구간의 크기와 1이 있는 것을 확인할 구간을 인자로 넘긴다.
아래와 같이 구간을 나누어 생각 한 뒤 (구간 시작과 l 중 큰 수) ~ (구간 끝과 r 중 작은 수)의 구간을 구한다. 이때 2s~3s는 0 이기 때문에 구하지 않는다.

그러면 (l, s) (s,2s) (3s, r) (4s, r)이다. 이 네 구간을 확인하면 되는데 이때 주의할 점은 n-1 번째 비트열이라고 생각하고 다음 함수를 호출하기 때문에 1이 있는 것을 확인할 구간의 인자(0, s,3s,4s)를 빼주어야 한다. 

 시작이 끝보다 큰 구간은 제외한다. n 이 1 이 되었다면 0번째 칸토어 비트열까지 내려온 것이므로 1을 반환한다.

 

---

문제를 보고 분할정복을 생각했지만 구상이 잘 되지 않았다. 보통 pseudo 코드를 작성하고 코드 입력을 하기 시작하는데 pseudo 코드 작성은 쉽지 않았다. 그래서 위처럼 그림을 그려보고 생각을 해보았더니 min과 max를 활용하면 되지 않을까 해서 했는데 되지 않았다. 보아하니 l과 r은 생각대로라면 맞는데 구간이 작아져서 크기가 5인데 l 과 r 이 15 16인 부분을 구할 수 없던 것이었다. 함수 호출을 할 때 구간의 시작점을 빼주니 문제가 쉽게 풀렸다!