2진수에서 1 누적합 구하기

문제

[09527] 1의 개수 세기

https://www.acmicpc.net/problem/9527

문제는 단순하다, 주어진 두 수 사이의 1의 개수를 세는 것이다.

분석

1의 개수를 세기 위하여, 0에서부터 15까지 2진수를 바꾸면 다음과 같다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	8
0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1	8
0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	8
0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	8
0	1	1	2	1	2	2	3	1	2	2	3	2	3	3	4	32

각 정수를 2진수를 바꾸면, 일반적으로 1씩 늘어가는 탓에 1의 개수가 불규칙해 보인다.

하지만 그렇다고 각 수별로 1의 개수를 세면, 주어진 수의 크기에 의하여 시간초과가 될 것이다.

따라서 좀 더 효율적으로 문제에 접근할 필요가 있다.

시점을 바꿔 각 자리 수 별로 보면 새로운 규칙을 발견할 수 있다.

• 제일 작은 비트는 [0] * 1, [1] * 1의 반복
• 그 다음 비트는 [0] * 2, [1] * 2의 반복
• 그 다음 비트는 [0] * 4, [1] * 4의 반복

즉 각 자리 값의 개수 만큼 0 과 1이 반복되는 것을 알 수 있다.

따라서 위와 같이 정리할 수 있다.

풀이

1의 누적합 개수를 세는 함수를 만드는데, 함수 내에서의 동작은 다음과 같다.

1. 지표는 2를 시작으로 반복문을 시작하는데, 지표가 주어진 숫자보다 커지면 종료한다.
2. 반복문 내에서는 주어진 수를 지표 값만큼 나눈 몫을 구하고, 몫에 지표의 절반 값을 곱해 더한다.
3. 주어진 수를 지표 값으로 나머지 연산한 값에서 지표의 절반 값을 빼고 더한다.
4. 하지만 4의 값이 음수일 경우 무시한다.
5. 반복문 내에서는 지표에 2를 곱하며 다음 반복문을 시작한다.

따라서 최종 코드는 다음과 같다.

https://github.com/onsoim/BOJ/tree/master/Solved/01000-09999/09527