분할 정복인 이유는 충분히 큰 n에 대해 2^n 길이의 문자열에서 시작해서, 반으로 나누어가며 그 왼쪽에 위치하면 반전이 없고, 오른쪽에 위치하면 반전이 하나 추가되는 형태로 찾아들어갈 수 있기 때문입니다. 이걸 비트로 표현하면 비트가 1인 것마다 반전이 생기는 것이기 때문에 그 개수를 세는 것만으로 찾는 값이 무엇인지를 알 수 있습니다.

그런데 이와 같은 풀이는 수를 1부터 세면 맞지 않고, 0부터 세야 맞기 때문에 1을 빼고 시작하는 것입니다.

@djm03178 답변 감사합니다. 생각하며 예시를 들었는데 아직도 모르겠습니다.

수열 : 0 1 1 0 1 0 0 1 ...

ex1) 5번째 위치의 값인 1을 알기 위한 과정

1. 5-1인 4의 비트값(0100) 중 1의 개수를 찾는다. 1개

2. 이후 1을 %2 한 값이 정답

Q. 투에-모스 수열과 찾고자 하는 값(n)의 비트값과의 연관관계가 궁금합니다.

찾고자 하는건 투에모스 수열인데 갑자기 정수의 비트값과 연관시키는게 이해가 되지 않습니다.

길이가 8인 것부터 시작해 봅시다. 즉, 0번째 수부터 7번째 수까지를 생각해 봅시다. 이를 반으로 나누면 0~3은 왼쪽에 있고, 4~7은 오른쪽에 있습니다. 4~7은 정의에 따라 0~3을 반전시킨 수열입니다. 4번째 수를 찾는 거니, 오른쪽으로 가야 하고 이는 왼쪽에서 4-4=0번째 수를 반전시킨 것과 같습니다. 다시 0~3을 반으로 나누면 0~1과 2~3으로 나눌 수 있고, 0은 이 중 왼쪽에 속하니 반전 없이 다시 왼쪽에서 0번째 수를 찾으면 됩니다. 마지막으로 0~1을 반으로 나누어 0과 1로 나누면 0은 왼쪽에 있고 반전이 없습니다. 그러면 지금까지 반전이 한 번 있었으니까 0번째 수인 0을 한 번 반전시킨 1이 답이 됩니다.

비트가 의미하는 건 2의 i제곱을 의미하는 것이고, 1인 비트의 수를 세는 건 위의 과정을 큰 i부터 한 단계씩 내려오면서 수행한 것과 같습니다. 즉, 비트가 1이면 오른쪽에 있다는 뜻이고, 0이면 왼쪽에 있다는 뜻입니다.

@djm03178 감사합니다. 반복해서 댓글 읽고 적어보니 이해됬습니다.!