[PS] 1의 개수 세기 / C++ (백준 9527번)

 

A, B가 $10^{16}$까지 이므로 $O(logn)$에 해결해야 한다.

$O(n)$은 무조건 시간초과.

 

풀이 과정

2진수에 나타나는 1의 개수를 구해보면 패턴을 찾을 수 있다.

1{1}, 2~3{1, 2}, 4~7{1, 2, 2, 3}, 8~15{1, 2, 2, 3, 2, 3, 3, 4} 까지만 봐도 패턴이 보인다.

d[i] = $2^i$ ~ $2^{i+1}-1$에서 1의 개수라고 했을 때 점화식은 $d[i]=d[i-1]*2+2^{i-1}$로 구할 수 있으며 이를 각 구역으로 봤을 때, 각 구역별로 절반씩 나눠보면 똑같은 패턴인 것이 확인된다.

8~15{1, 2, 2, 3, 2, 3, 3, 4}를 반으로 나누면 8~11{1, 2, 2, 3}, 12~15{2, 3, 3, 4}로 나눠지고 반으로 나눈 right 집합은 left+1임을 알 수 있다. 이를 또 쪼개봐도 8~9{1, 2}, 10~11{2, 3}으로 패턴은 성립한다.

이 패턴을 이용하여 재귀식을 짜주면 된다.  

f(18, 30)

 18~30을 재귀로 돌린다 가정했을 때 다음과 같이 범위가 맞을 때까지 반으로 나누고, 최종적으로 값을 다 더하면 범위 내의 1의 개수를 구할 수 있다.

 

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll d[101];

ll f(ll st, ll en, ll cmp, ll tar_front, ll tar_back) {
	if (st == tar_front && en == tar_back)return cmp;
    
	ll mid = (st + en) / 2, cmp_left = (cmp - (en - st + 1) / 2) / 2, cmp_ret = 0;
	
    if(st<=tar_front&&tar_front<=mid)
		cmp_ret += f(st, mid, cmp_left, tar_front, tar_back < mid ? tar_back : mid);
	if (en >= tar_back && tar_back >= mid + 1)
		cmp_ret += f(mid + 1, en, cmp - cmp_left, tar_front > (mid + 1) ? tar_front : (mid + 1), tar_back);

	return cmp_ret;
}
int main()
{
	ll A, B, dap = 0;
	scanf("%lld %lld", &A, &B);
	d[0] = 1;
	if (A == 1) {
		A = 2;
		dap = 1;
	}
	for (int i = 1; ; i++) {
		ll i_pow = pow(2, i);
		if (B < i_pow)break;
		d[i] = d[i - 1] * 2 + i_pow / 2;
		ll st = i_pow, en = i_pow * 2 - 1;
		if (st <= A && A <= en) {
			if (B < en)
				dap += f(st, en, d[i], A, B);
			else {
				dap += f(st, en, d[i], A, en);
				A = en + 1;
			}
		}
	}
	printf("%lld\n", dap);
	return 0;
}