[백준] Q9527 1의 개수 세기 JAVA

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

9527번: 1의 개수 세기

1. 문제의 유형 및 이해

bitmasking, dp, 누적합

f(x) = x를 이진수로 표현했을 때 1의 개수.

$A<=x<=B$를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수 합을 구해보자.

 

$A<=x<=B$ 를 통해서 0부터 B까지의 모든 1의 개수를 구하고 0부터 A-1까지의 1의 개수를 빼주면 답을 구할 수 있겠다고 생각했다.

그렇다면 어떠한 x까지의 1의 개수를 구하는 것이 문제였고 이를 dp를 통해 해결했다.

2. 문제 접근 방법

2진수가 커지는 형태와 1의 개수에 집중해서 보자.

1의 개수

4자리일 때 1의 개수를 보자. 

3자리일때 1이 반복해서 2번 나타나고 빨간 박스에 새로운 1이 나타나고 있다.

즉 dp[x] = x자리일 때 1의 개수 라고 정의한다면

dp[x] = dp[x-1] *2 + $2^{x-1}$ 이 된다. 

 

이렇게 되면 우리는 어떠한 자리수에 대해 해당 자리수로 나타낼 수 있는 모든 1의 개수를 구할 수 있다.

 

다음 21일때의 예시를 한번 보자.

21의 예시

어떠한 자리수에 1이 있다면, 위와 같은 모양이 될거다.

즉 21인 가장 아래부터 위까지 쭉 올라가면서 0의 개수를 센다고 했을 때, 하나 하나 차례대로 보면된다.

우리가 처음에 dp를 구했던 것 처럼 가장 앞자리가 0인 애들은 일단 지금 자리수 x보다 x-1인 애들 모두를 포함한다.

이후 앞자리가 1인 1의 개수는 초록색 박스 개수만큼 있겠다. 여기까지가 빨간 박스를 구한 형태이다

 

헷갈린다면 이렇게 생각하면 된다. 위에서 구했던 방식처럼

앞자리가 0일때 개수는 현재 자리수보다 작은 dp[x-1]로 구했었다.

그다음 앞 자리가 1인 1의 개수를 세어줄 때는 $2^{x-1}$로 구했었는데 이번에는 초록색박스개수만큼만 구해주면 되는 거다.

앞자리가 1인 애들에 대해서 나머지 초록색 안쪽 부분의 1의 개수를 구해야 하는데 위의 dp를 구할 때에는 어차피 dp[x-1]개로 꽉 채워서 있었기 때문에 쉽게 구할 수 있었지만 이번엔 저 '0101'을 처리해야한다.

 

'0101'을 구할때는 방금 우리가 구한 것 처럼 똑같이 반복해서 구하면되는 분할정복처럼 생각하면 된다.

조금 더 나아가보자면 '0101' 즉, 5에 대해 다시 구하면 되는데 위와 같은 방식으로 구하게 되면, 

5 구하기

다음과 같이 반복하게 된다.

즉 우리가 생각할껀, 어떤 자리수가 1일 때 빨간박스에 대해 계산해주고,

나머지 초록색 부분에 대해서만 다시 생각해주면 된다는 뜻이다.

 

bit연산을 통해 해결하도록 한다.

이 때, 주어지는 값이 $10^{16}$으로 log2를 취하게 되면 약 53.xxxx으로 53자리로 표현가능하다.

혹시 몰라서 55까지 했다.

미리 dp배열을 통해 구해주고 count함수를 통해 개수를 return받아 답을 도출한다.

package solvedac.level5.gold2;

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

/**
 * @문제번호 : Review_9527
 * @문제이름 : 1의 개수 세기
 * @난이도 : Gold II
 * @date : 2022-02-26 오후 1:18
 * @author : pcrmcw0486
 * @문제이해
 * A<=X<+B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수 합을 구하는 프로그램
 *  f(x) = x 를 이진수를 표현했을 때 1의 개수
 * 규칙이 존재한다.
 * @알고리즘
* dp bitmasking?
 * @접근방법
 * 1의 개수
*/
public class Main {
    static long[] dp = new long[56];
    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());
        init();
        long ans = count(B) - count(A - 1);
        System.out.println(ans);
    }

    public static long count(long num) {
        int pos = 55;  //자리수
        long cnt =0;
        while (num > 0) {
            if ((num & (1L << pos)) != 0) {
                cnt += dp[pos] + (num-(1L <<pos)) + 1L;
                num ^= (1L<<pos);  //masking &=(1<<pos)-1;
            }
            pos--;
        }
        return cnt;
    }
    public static void init(){
        dp[1] = 1;
        for (int i = 2; i < 56; i++) {
            dp[i] = dp[i - 1] * 2 + (long)Math.pow(2, i - 1);
        }
    }
}