9527 1의 개수세기

알고리즘(수학)

1. 2^n 마다 규칙이 있음
2. f(n)을 2^n ~ 2^(n+1)-1 에서의 1의 개수라고 한다면, f(n) = 2^n + f(i) ( 0 <= i <= n-1 ) 이 성립한다.
3. 그리고 들어오는 수 A,B에 대해
	(1~B 까지의 1의 개수) - (1~A-1 까지의 1의 개수) 를 하면 값이 나온다.
4. 2에서의 규칙에따라 end가 주어지면 0에서 end까지의 1의 개수를 구하는 함수를 선언한다.
	-> 이때 end 미만의 최대 2^n의 n를 구한다.
	-> 2에서의 규칙에 따라 0~n까지의 f(n)을 구한다.
	-> 그럼 나머지 2^(n+1) ~ end 에서의 1의 개수를 구하면 된다.

5. 나머지를 구하는 함수를 선언한다. 2^(n+1)에서 end까지 구하면 된다.
	-> 이때 2^(n+1) ~ end 사이의 값들의 맨앞은 전부 1이고, 개수는 end - 2^(n+1) + 1이다.
	-> 그리고 그 맨앞의 1을 떼고 보면, 0부터 end - 2^(n+1) 까지의 이진수 분포와 동일하다
	-> 따라서 다시 end - 2^(n+1)을 위 4번 함수에 넣으면 된다.

코드

#include <iostream>
#include <cmath>
 
using namespace std;
 
long long a, b;
long long DP[55];
 
long long getN(int N);
long long countOne(long long end);
long long getRest(long long start, long long end);
 
int main() {
	cin >> a >> b;
	DP[0] = 1;
 
	cout << countOne(b) - countOne(a-1) << endl;
}
 
long long countOne(long long end) {
	if (end <= 2)
		return end;
 
	int n = 0;
	long long temp = 1;
	while (temp < end) {
		temp *= 2;
		n++;
	}
	if (temp - end <=1)
		n -= 1;
	else
		n -= 2;
 
	long long result = 0;
	for (int i = 0; i <= n; i++)
		result += getN(i);
 
	result += getRest(pow(2, n+1), end);
 
	return result;
}
 
long long getN(int N) {
	if (N == 0)
		return 1;
	if (DP[N] != 0)
		return DP[N];
 
	long long result = pow(2, N);
	for (int i = N - 1; i >= 0; i--)
		result += getN(i);
 
	return DP[N] = result;
}
 
long long getRest(long long start, long long end) {
	if (start > end)
		return 0;
 
	return end - start + 1 + countOne(end - start);
}