[백준] 9527: 1의 개수 세기 - JAVA

in Algorithm on 수학

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

풀이

자연수 A부터 B까지 모든 수에 대해 이진수로 표현했을 때 1의 개수를 구해야한다.

자연수의 범위는 10의 16제곱까지였다.

2의 54제곱이 10의 16제곱을 넘어서 이진수로 54자리수까지 담는 배열을 만들었다.

dp[i] = (dp[i - 1] << 1) + (1L << i);

배열의 점화식은 위와 같다. i자리수는 i-1자리수의 모든 경우의 앞에 1을 붙이면 되기 때문이다.

B까지의 개수에서 A-1까지의 개수를 빼주면 정답이다.

하지만 예를 들어 자연수 14가 주어지면 3자리까지의 개수를 더하고 나머지를 더 구해줘야 한다.

이진수들을 써본 결과 규칙을 찾았고 다음과 같은 식으로 계산할 수 있었다.

return dp[digit - 1] + diff + count(n - num);

digit는 n보다 작은 이진수의 자리수 이고, diff는 n보다 작은 2의 제곱수와 n의 차이이다.

메모리: 14244KB

시간: 124ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

public class Main {
    static long[] dp;

    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());

        dp = new long[55];
        dp[0] = 1;
        for (int i = 1; i < 55; i++) {
            dp[i] = (dp[i - 1] << 1) + (1L << i);
        }

        long ans = count(B) - count(A - 1);

        System.out.println(ans);
    }

    private static long count(long n) {
        if (n == 0 || n == 1) {
            return n;
        }

        int digit = 0;
        long num = 1;
        while (num * 2 <= n) {
            num *= 2;
            digit++;
        }

        long diff = n - num + 1;

        return dp[digit - 1] + diff + count(n - num);
    }

}