[백준 1407] 보석도둑 (자바)

백준 1407번: 보석 도둑

문제 설명

주어진 범위 [a, b]에서 수의 이진수 표현에서 1의 개수를 구하는 문제입니다. 예를 들어, a=5, b=9라면 5에서 9까지의 수의 이진수 표현에서 1의 개수를 모두 더한 값을 출력합니다.

문제 접근 방법

1. 각 수의 이진수 표현에서 1의 개수를 효율적으로 계산하기 위해 동적 계획법을 사용합니다.
2. 1부터 b까지의 수에 대해 이진수에서 1의 개수를 누적합으로 저장합니다.
3. [a, b] 범위의 수에서 1의 개수를 구하기 위해 b까지의 누적합에서 a-1까지의 누적합을 뺍니다.

시간 복잡도 분석

O(N log N)

• 각 수를 2로 나누어 1의 개수를 세는 과정은 log N입니다.
• 이를 모든 수에 대해 반복하므로 시간 복잡도는 O(N log N)입니다.

해결 방법

아래는 주어진 범위에서 이진수 표현에서 1의 개수를 구하는 Java 코드입니다:

package re_02;

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

public class BOJ_1407_보석도둑 {
    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());
        List<Long> dp = new ArrayList<>();
        dp.add(0L);
        dp.add(1L);

        List<Long> list = new ArrayList<>();
        list.add(0L);
        list.add(1L);

        for (int i = 2; i <= b + 1; i++) {
            int count = 0;
            int j = i;
            while (j > 1) {
                if (j % 2 == 0) {
                    count++;
                    j = j / 2;
                } else {
                    break;
                }
            }
            long pow = (long) Math.pow(2, count);
            list.add(pow);
            long value = dp.get(dp.size() - 1) + pow;
            dp.add(value);
        }

        int answer = (int) (dp.get((int) b) - dp.get((int) a - 1));

        System.out.println(answer);
    }
}