[백준] 9527번 - 1의 개수 세기 (Gold 2)

문제 링크

백준 9527번 - 1의 개수 세기 (Gold 2)

문제 설명

주어진 두 자연수 A, B가 있다.
A 이상 B 이하의 x를 이진수로 표현했을 때 나타나는 1의 개수를 모든 x에 대해 합한 값을 구하시오.
A, B의 범위는 $1 \leq A \leq B \leq 10^{16}$이다.

정답 코드 및 설명

1부터 X까지의 모든 자연수를 이진수로 표현했을 때 나타나는 1의 총 개수를 $f(X)$라고 하자.
그러면 A 이상 B 이하의 범위에서 나타나는 1의 개수의 총 합은 $f(B) - f(A - 1)$이 된다.
따라서, $f(X)$만 구할 수 있으면 충분하다.

1부터 $2^{n} - 1$까지의 범위에서 나타나는 1의 총 개수는 $n * 2^{n}/2$이다.
0부터 $2^{n} - 1$까지의 각각의 수를 앞에 0을 채워넣어 n자리로 만들면 0과 1이 나오는 빈도수가 정확히 같으며, 0을 이진수로 바꿨을 때는 1이 나타나지 않기 때문이다.
이제 $2^{n} \leq X < 2^{n+1}$인 X에 대해, $2^{n}$ 이상 X 이하인 모든 자연수를 이진수로 표현했을 때 나타나는 1의 개수의 합을 구하면 된다.
먼저, 각 자연수를 이진수로 바꿨을 때 첫 자리에서 나오는 1이 총 $X - 2^{n} + 1$개이다.
첫 자리가 아닌데서 나오는 1은 0부터 $X - 2^{n}$까지에서 나오는 1의 개수, 즉 $f(X - 2^{n})$과 같다.
이제 재귀적인 방식으로 f(X)를 구할 수 있다.

코드로 구현하면 아래와 같다. A, B가 $10^{16}$ 이하이므로 $2^{63} - 1$보다 작아서 long 변수로 충분하다.
시간 복잡도는 $O(\log A + \log B)$이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ9527 {
    long a, b;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        a = Long.parseLong(st.nextToken());
        b = Long.parseLong(st.nextToken());
    }

    long count(long a) {
        if (a == 0 || a == 1) return a;
        int digits = 0;
        long powOf2 = 1;
        while (powOf2 * 2 <= a) {
            powOf2 *= 2;
            digits++;
        }
        return digits * powOf2 / 2 + (a - powOf2 + 1) + count(a - powOf2);
    }

    void solution() throws IOException {
        input();
        System.out.println(count(b) - count(a - 1));
    }

    public static void main(String[] args) throws IOException {
        new BOJ9527().solution();
    }
}