[Baekjoon 9527] 1의 개수 세기 - JAVA

 

 

[Gold II] 1의 개수 세기 - 9527

문제 링크

성능 요약

메모리: 14192 KB, 시간: 124 ms

분류

비트마스킹, 수학, 누적 합

문제 설명

두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오.

즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자.

 \[
\sum_{x=A}^{B}f(x)
\]

입력

첫 줄에 두 자연수 A, B가 주어진다. $(1 ≤ A ≤ B ≤ 10^{16})$

출력

1의 개수를 세어 출력한다.

문제 풀이

문제의 핵심은 아래와 같다.

1. A이상 B이하의 수들을 2진수로 표현할 때 1의 개수 결과로 출력한다.
2. A와 B의 입력 범위가 경까지 간다.(= 자료형이 int가 아니다.)

필자는 dp를 이용한 풀이와 재귀를 통해 1의 개수를 계산하는 방법을 사용해 문제를 풀었다.

DP문제풀이의 점화식은 아래와 같다.

dp[0] = 1; (초기값)
dp[i] = (dp[i - 1] << 1) + (1L << i); (i > 0)

DP를 사용한 코드

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

public class Main {
    static long[] dp = new long[55];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long A = Long.parseLong(st.nextToken()); // startRange를 A로 바꿔줌
        long B = Long.parseLong(st.nextToken()); // endRange를 B로 바꿔줌

        calculateDP();
        long result = countOnesInRange(B) - countOnesInRange(A - 1); // startRange를 A로 바꿔줌
        System.out.print(result);
    }

    static long countOnesInRange(long n) {
        long count = n & 1;
        int size = (int) (Math.log(n) / Math.log(2));
        for (int i = size; i > 0; i--) {
            if ((n & (1L << i)) != 0L) {
                count += dp[i - 1] + (n - (1L << i) + 1);
                n -= (1L << i);
            }
        }
        return count;
    }

    static void calculateDP() {
        dp[0] = 1;
        for (int i = 1; i < 55; i++)
            dp[i] = (dp[i - 1] << 1) + (1L << i);
    }
}

재귀를 사용한 코드

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

public class Main {
    public static long calculateCount(long number) {
        if (number == 0 || number == 1) return number;
        int digitCount = 0;
        long powerOf2 = 1;
        while (powerOf2 * 2 <= number) {
            powerOf2 *= 2;
            digitCount++;
        }
        return digitCount * powerOf2 / 2 + (number - powerOf2 + 1) + calculateCount(number - powerOf2);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());

        long result = calculateCount(B) - calculateCount(A - 1);

        System.out.println(result);
    }
}