백준 BOJ 9527 - 1의 개수 세기

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

9527번: 1의 개수 세기

고민을 오래 해봐야 하는 문제

수의 범위가 크다.

일단 수의 범위가 매우 큰 편이라서, 전처리를 통해서 시간을 아낄 생각을 해봐야 한다.

대부분의 변수에서 long long 형이 필요하니까, 그냥 모든 변수 자료형을 ll으로 통일하면 깔끔해진다.

 

cnt[k] 를 비트 k개 범위(0~2^k-1) 의 수들에서 등장하는 2진수 1의 개수의 합

으로 정의한다.

 

숫자 K가 i개의 비트로 이루어진 수일때,

그 하위 비트에 1의 갯수가 j개인 경우의 수는 nCr(i,j) 이고,

각각의 경우의 수에 1의 갯수가 j개 있으므로

cnt[i] 는 모든 j에 대해서 nCr(i,j) * j 를 계산한 것의 합이 된다.

 

다른 해답으로 2의 지수 꼴로 O(N)에 테이블을 채울수 있는 것 같은데,

개인적으로는 조합을 사용한 풀이가 보다 깔끔한 듯 하다.

 

10^16은 2^59보다는 확실히 작은 숫자이니,

깔끔하게 cnt의 크기는 60정도로 설정해주면 좋을것 같다.

---

이렇게 cnt[k]를 구해준 다음에,

입력으로 들어온 수 S와 E에 대해서

[0,E] 까지에서의 1의 개수,

[0,S) 까지에서의 1의 개수를 각각 구해주면 정답을 구할 수 있다.

 

수 E의 a번째 비트가 1으로 켜져있는 경우,

예시에서는 a를 4로 정하겠다.

 

0a000 부터

0a111 까지 1의 갯수는 미리 구해뒀던 cnt 배열을 통해

 

cnt[a-1] 로 한번에 구해줄 수 있고,

 

00111 이후의,

01000

01001 등등의 a번째 비트가 켜져있는 수들의 갯수를

X-2^a+1 으로 구해줄 수 있다.

 

이 둘을 서로 더해서 변수에 모든 a에 대한 합을 구해주면,

정답을 얻을 수 있다.

 

이때 다음 계산에서 X가 불필요하게 커지는걸 막기 위해서

사용한 켜져있는 비트 a는 0으로 변경해줘야 한다.

 

난해한편이라서 설명도 좀 어려웠던;;

 

https://degurii.tistory.com/158

[BOJ] 백준 9527 1의 개수 세기

그림자료를 활용하신 분이 있어서

첨부해본다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll cnt[60] = {0}; // cnt[k] -> 비트k개 범위에서 (0~2^k-1) 1의 개수의 합
ll ncr[60][60] = {0};

ll nCr(ll n, ll r){
	if(ncr[n][r] != 0) return ncr[n][r];
	if(n==r || r==0) return 1;
	return ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);
}

ll prefix(ll K){
	ll ret = K%2;
	
	for(ll i=59; i>0; i--){
		if(K & (1LL << i)){
			ret += cnt[i] + (K-(1LL<<i)+1);
			K -= 1LL << i;
		}
	}
	
	return ret;
}

int main(){
	for(ll i=1; i<=55; i++){
		for(ll j=1; j<=i; j++){
			cnt[i] += nCr(i,j)*j;
		}
	}
	
	ll S,E;
	cin >> S >> E;
	cout << prefix(E)-prefix(S-1);
	return 0;
}