9527 - 1의 개수 세기

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

9527번: 1의 개수 세기

 과정

1. 2진수로 생각을 해보자.
   1. 11111(2)을 기준으로 보면 00000 -> 00001 -> 00010 -> ... 으로 진행 되게 된다.
   2. 1자리 -> 1 1개, 2자리 -> 10 11 01 4개
   3. 맨 앞 1의 경우 이전 자리 경우의 수 -> 2^n, 맨 앞이 0, 1 2가지의 경우 이므로 dp[n-1] * 2로 진행하게 된다.
   4. 단순 공식으로 변환해보면 dp[n] = dp[n-1]*2 + 2^n 이 나오게 된다.
2. 10101(2)의 1의 개수를 생각해보자.
   1. 10000(2)의 경우 이전 4자리 dp[3]과 맨 앞자리 1이 101(2) + 1(100(2)도 포함) 만큼 나오게 된다.
   2. 100(2)의 경우 이전 2자리 dp[1]과 맨 앞자리 1이 1(2) + 1 만큼 나오게 된다.
3. calc(B) - calc(A-1)을 진행하면 된다. calc는 10101(2)의 전체 1이 나오는 등장 횟수를 구해주는 함수다.

코드

#include<iostream>

using namespace std;

long long A,B;
long long dp[55];

void input(){
    cin>>A>>B;
}

long long calc(long long num){
    long long sum = num & 1;

    for(int i = 54 ; i > 0 ; --i){
        if(num & (1LL << i)){
            num -= 1LL << i;
            sum += dp[i-1] + num + 1; 
        }
    }
    return sum;
}



void solution(){
    dp[0] = 1;
    for(int i = 1; i< 55 ; ++i){
        dp[i] = dp[i-1] * 2 + (1LL << i);
    }

    long long ans = calc(B) - calc(A-1);
    cout<<ans<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    solution();

    return 0;
}

참고

https://degurii.tistory.com/158