[BOJ] 1의 개수 세기

1의 개수 세기

TimeLimit	MemoryLimit	Condition	TAG
1s	128MB	1 ≤ A ≤ B ≤ 10^16	Dynamic Programming, Bit Masking

두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자:
$\sum_{x = A}^{B} f (x)$

와… 오랜만에 많이 막힌 문제였습니다. 허허… 요즘 골드 문제도 이렇게 막힐 수 있다는 것을 알아갑니다..

일단 시간 초과를 피하기 위해서 dp를 이진법의 bit 별로 개수를 세주고, 그걸 활용하는 식으로 시간을 좀 단축 시켰습니다.

일단 제가 짠 코드를 이해하려면 이진법에 대해서 알아야 하는데, dp 채우는 코드는 아마 식을 세우다 보면 자연스럽게 얻어지는 식이구요. 위에 solution은

그냥 현재 들어온 수에 대해서 최상위 비트를 보고있다고 생각하고, 그 하위 비트들은 한 cycle을 돌렸으니까 하나의 확정된 cycle을 더해주고, 그리고 최상위 비트 제외하고 처리합니다.

이후에는 최상위 비트가 켜져있으니 1을 더해주고요. 그 후에는 하위 비트로 내려가면서 다 처리하는 로직을 따릅니다.

생각보다 간단한 로직이긴 합니다만… 뭔가 꽤 막혀서 고민을 했던 문제였네요 허허허허허헣…

언제나 즐거운 PS 되시길 바랍니다.

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = unsigned long long;




ll a, b;
ll memo[100];
ll pow(int up){
    return 1ULL << up;//current;
}

ll solution(ll current) {
    if (current == 0) return 0;
    
    int size = 0;
    for (int i = 0; i <= 63; i++)
        if (current & (1ULL << i)) size = i;
    
    
    ll result = 0;
    result = memo[size];
    current = current - (1ULL << size);
    result += current + 1;
    
    result += solution(current);
    
    return result;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> a >> b;
    
    memo[0] = 0;
    memo[1] = 1;
    memo[2] = 4;
            
    
    for(int i = 3; i < 64; i++){ memo[i] = memo[i-1]*2 + pow(i-1);}
    

    cout << solution(b) - solution(a-1);

    return 0;
}