[백준 9527] 1의 개수 세기

문제 링크 => 9527번: 1의 개수 세기 (acmicpc.net)

9527번: 1의 개수 세기

 

수학을 이용한 문제이다.

 

먼저 규칙성을 발견하면 다음과 같다.

 

(1) 2^0 ~ 2^1 - 1 일 때 1의 개수의 합 : 1 = 1 + 0

 

(2) 2^1 ~ 2^2 - 1 일 때 1의 개수의 합 : 3 = 2 + 1

 

(3) 2^2 ~ 2^3 - 1 일 때 1의 개수의 합 : 8 = 4 + 4

 

(4) 2^3 ~ 2^4 - 1 일 때 1의 개수의 합 : 20 = 8 + 12  (아래 table을 보자)

 

8	1	0	0	0
9	1	0	0	1
10	1	0	1	0
11	1	0	1	1
12	1	1	0	0
13	1	1	0	1
14	1	1	1	0
15	1	1	1	1

 

위와 같이 8 + 12 = 2^3 + 3 * 2^(3 - 1) 으로 20을 유도할 수 있다.

 

즉, 이걸 일반화 한다면 다음과 같다.

 

2^n ~ 2^(n + 1) - 1 일 때 1의 개수의 합 : 2^n + n * 2^(n - 1)

 

 

 

그러나 문제점이 있다.

 

 

1 ~ 13 을 더할 때 1의 개수의 합을 구할 때 위에서 발견한 방법을 이용한다면... (result = 0)

 

먼저 1 ~ x 에 대한 1의 총 합을 구하는 함수 Solution(x) 라고 정의하자.

(Solution(x) => 1 에서 x 까지의 1에 대한 총 합을 반환하는 함수)

 

(0) main 에서 Solution(13) 을 호출 (result = Solution(13))

     그리고 Solution 함수에 대한 처리가 진행된다.

 

(1) 2^0 ~ 2^1 - 1 에 전부 속하므로 result += 1

 

(2) 2^1 ~ 2^2 - 1 에 전부 속하므로 result += 3

 

(3) 2^2 ~ 2^3 - 1 에 전부 속하므로 result += 8

 

(4) 2^3 ~ 2^4 - 1 에 부분적으로 속하므로 result += ??? (위 방법만으로는 알 수 없음)   

 

부분적으로 속하는 경우에 대한 처리가 필요하다.

 

8	1	0	0	0
9	1	0	0	1
10	1	0	1	0
11	1	0	1	1
12	1	1	0	0

 

여기서 알 수 있는 점은 다음과 같다.

 

(1) 8, 9, 10, 11, 12 에 대한 MSB는 항상 1이라는 점이다.

     즉, result += (12 - 8 + 1) 에 대한 처리를 할 수 있다.

 

(2) MSB 를 제외한 나머지 bit들을 살펴보자.

     나머지 bit들에 대한 1의 개수들의 합은 1 ~ 4 에 대한 1의 개수들의 총 합이 되어버린다.

 

즉, recursion 문제이므로 나머지 bit들에 대한 1의 개수들의 합은 다음과 같이 재귀적으로 구할 수 있다.

 

result += solution(12 - 8)   <= 즉, 1 ~ 4 에 대한 1의 총 합을 재귀적으로 더해줘야 한다.

 

 

Solution Code 

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

long long power[100];

long long solution(long long N) 
{
	if (N == 0)
		return 0;
	if (N == 1)
		return 1;

	long long x, ret, tmp;

	x = 1, ret = 1;
	tmp = N / 2;
	while (tmp != 1) {
		ret += power[x] + x * power[x - 1];
		tmp /= 2;
		x++;
	}

	return ret = ret + N - power[x] + 1 + solution(N - power[x]);
}

int main(void) 
{
	int i;
	long long A, B;
	scanf("%lld %lld", &A, &B);

	power[0] = 1;
	for (i = 1; i < 100; i++)
		power[i] = power[i - 1] * 2;

	printf("%lld", solution(B) - solution(A - 1));

	return 0;
}