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

문제 링크

www.acmicpc.net/problem/9527

9527번: 1의 개수 세기

 

풀이

1) 1부터 x 이하 모든 수의 1의 개수를 구해주는 함수 go를 구현합시다.

2) go$(B)$ - go$(A-1)$ 를 구해주면 됩니다!

 

이제 go함수를 만드는 방법을 알아봅시다.

 

1. 누적합 구하기

우선 최상위 비트가 $i$번 이하인 모든 수의 1의 개수의 합을 누적합으로 구해줘야 합니다.

편의상 $i$는 0부터 시작한다고 합시다.

 

이를 어떻게 구할 수 있을까요?

그림을 보면 최상위 비트가 $i$번인 모든 수의 앞쪽이 그보다 작은 수들로 반복되는 걸 볼 수 있습니다.

그리고 최상위 비트가 $i$번인 수는 정확히 $2^{i}$개입니다.

따라서 최상위 비트가 $i$번 이하인 모든 수의 1의 개수의 누적합을 다음처럼 구할 수 있습니다.

$d[i] = 2\cdot d[i-1] + 2^{i}$

 

 

좀 더 쉽게 풀어보면

$d[i] = d[i-1] +$($i$번 비트를 뺀 나머지 반복되는 수들의 1의 개수) $+$ (i번째 비트에 나타나는 1의 수) 

라고 볼 수 있습니다. 어질어질하죠?

 

이렇게 누적합을 구해주면 절반은 완성입니다.

 

2. 정답 구하기

이제 다음은 어떤 수 $x$이하의 모든 1의 개수의 합을 구해주는 건데요.

26을 예시로 들어봅시다. 이진수로 하면 11010(2) 구요.

 

비트 별로 개수를 처리하는 방식입니다. 큰 비트부터 순회합니다. 만약 $i$번 비트가 켜져 있다, 예를 들어 4번이 켜져(1xxxx)있으면, 10000(2) 미만 모든 수의 1의 개수와, 4번 비트가 켜져 있는 수의 개수를 더해줍니다.

 

말로만 하면 헷갈리니까 그림으로 보겠습니다.

 

이런 상황입니다. 이 경우 10000(2) 미만의 모든 수의 1의 개수를 아까 구한 누적합으로 구할 수 있고, 그 이상의 수들(보라색 박스)은 $i$번 비트가 켜져 있으니 개수만큼 정답에 더해주면 됩니다.

 

위를 바탕으로 4번 비트에서 처리하는 1의 개수는

ans += (10000(2) 미만 모든 수의 1의 개수의 합) + (더해줘야 하는 4번 비트의 개수)

가 됩니다. 뒤쪽의 더해줘야 하는 4번 비트의 개수는 $x-2^{4}+1$로 쉽게 구할 수 있습니다.

코드로 표현하면

ans += $d[i-1] + (x-(1$<<$i)+1)$ 이 되겠네요.

 

그 후 $x$에서 $2^{4}$를 빼주고 다음 3번 비트를 봅시다.

아까 누적합을 구할 때 말했듯 각 비트 별로 항상 그 앞의 수가 반복됩니다. 따라서 4번 비트를 처리할 때와 마찬가지로 1000(2) 미만의 모든 수의 누적합을 더해주고, 1010(2)을 기준으로 1000(2) ~ 1010(2)의 개수를 더해주면 됩니다.

 

나머지 비트도 다음과 같은 방식으로 처리가 가능합니다.

 

 

만약 어떤 비트가 0이면, 그보다 작은 수가 앞에 존재하지 않기 때문에 처리하지 않아도 됩니다.

그리고 0번 비트는 $x$가 홀수인지 짝수인지 판단해 따로 더해줍시다.

 

이번 문제는 푸는 것보다 풀이를 쓰는 게 훨씬 어려운 문제였습니다..

이해 안 가는 부분이 있다면 댓글로 물어봐주세요!

 

 

정답 코드

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

ll a, b;
ll d[55];

ll go(ll x, ll i = 54) {
    ll ans = x & 1;
    for (; i > 0; i--) {
        if (x & (1LL << i)) {
            ans += d[i - 1] + (x - (1LL << i) + 1);
            x -= 1LL << i;
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    d[0] = 1;
    for (ll i = 1; i < 55; i++) {
        d[i] = d[i - 1] * 2 + (1LL << i);
    }
    cin >> a >> b;
    cout << go(b) - go(a - 1);
}