1의 개수 세기( BOJ 9527 )

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

9527번: 1의 개수 세기

 

문제 파악하기

주어진 자연수 A, B 사이의 모든 숫자를 이진수로 표현했을 때, 사용되는 모든 1의 개수를 세는 프로그램입니다. 이렇게 특정 구간 내에 조건을 만족하는 값의 개수를 세는 문제에서는 주로 누적합을 구하는 알고리즘을 활용해서 문제를 해결하며, 이번 문제 역시 비슷한 방식을 사용하면 문제를 해결할 수 있습니다. 여기서 말하는 누적합을 구하는 알고리즘이란 구하고자 하는 구간의 최댓값까지 누적합을 구한 다음, 구간의 최솟값 이전까지의 누적합을 빼서 특정 구간의 누적합을 구하는 알고리즘을 의미합니다. 예를 들어, 구간 [A:B]의 누적합을 구하고자 한다면 우선 [1:B]까지의 누적합을 구한 다음, [1:A-1]까지의 누적합을 구해서 빼주면 우리가 원하는 [A:B]의 누적합을 구할 수 있게 됩니다. 이 알고리즘이 이번 문제에서 어떻게 적용되는지 차근차근 살펴봅시다.

 

문제 해결하기

이 문제를 풀기 위해서는 이진수의 특징을 알고 있어야합니다. 이진수란 0과 1만을 사용해서 숫자를 표현하는 수체계를 의미하며, 0과 1밖에 없기 때문에 모든 자릿수는 0과 1이 주기적으로 반복됩니다. 아래는 0 ~ 15까지의 십진수를 이진수로 표현한 표를 보면서 특징을 찾아보세요.

 

특징을 찾아보았나요? 우선, 1의 자리 숫자는 항상 [01]을 반복합니다. 그리고 2의 자리 숫자는 [0011]이 반복됨을 찾을 수 있습니다. 마찬가지로 4의 자리, 8의 자리, 16의 자리 모두 [0....01....1]의 형태로 숫자가 반복되고 있음을 찾을 수 있습니다. 따라서, 우리는 1의 자리부터 현재 숫자(K)가 사용할 수 있는 자릿수의 숫자까지 모두 찾아보면서 얼마나 많은 패턴이 반복되고 있는지 확인하면 0부터 현재 숫자(K)까지의 숫자에 사용된 1의 개수를 파악할 수 있습니다.

 

예를 들어, 12를 표현하는데 사용된 1의 개수를 파악해봅시다. 여기서 우리는 항상 패턴은 0부터 시작한다는 사실을 간과해서는 안됩니다. 따라서, 12라는 숫자는 우리가 사용하는 알고리즘에서는 13번째 숫자이기 때문에 13이라는 값을 가지고 계산을 시작합니다. 우선, 13번째 숫자의 1의 자리는 총 6개의 패턴을 가지고 있으며, 현재 1의 자리 숫자는 0이 됩니다. 따라서, 1의 자리에서 사용되는 숫자의 개수는 총 6개 입니다.

2의 자리에서 등장하는 숫자패턴은 [0011]입니다. 따라서, 13번째 숫자인 12까지 [0011] 패턴이 총 3번 사용되며, 현재 2의 자리 숫자는 0이 됩니다. 따라서 2의 자리에서 사용된 1의 개수는 총 6개 입니다.

4의 자리에서 등장하는 숫자패턴은 [00001111]이며, 13번째 숫자인 12까지 총 1번의 패턴이 사용되었으며, [00001]의 패턴이 부분적으로 사용되었습니다. 그렇기에 4의 자리에서 사용된 1의 개수는 4 + 1 = 5개 입니다.

마지막으로 8의 자리에서 사용된 숫자 패턴은 [0000000011111111]이며, 현재 [0000000011111]의 부분 패턴이 사용되었습니다. 따라서, 8의 자리에서 사용된 1의 개수는 총 5개입니다.

이렇게 각각 구한 1의 개수를 모두 더하면 총 6 + 6 + 5 + 5 = 22개가 됩니다.

 

이렇게 입력된 두 수에 대해 0부터 시작한다는 기준점을 잡은 다음, 적절하게 구간을 제외해주면 문제를 해결할 수 있습니다. 문제를 해결하는 기본적인 소스코드는 다음과 같습니다. 

 

소스코드

#include <stdio.h>
#define lint long long int
 
lint A, B;
 
lint sv(lint k) {
    lint f, ret=0;
 
    f = 2;
    while(f<=k) {
        ret += (k/f)*(f/2);
        if(k%f >= f/2) ret += (k%f - f/2);
 
        f*=2;
    }
    if(k%f >= f/2) ret += (k%f - f/2);
 
    return ret;
}
 
int main() {
    scanf("%lld %lld", &A, &B);
 
    printf("%lld", sv(B+1) - sv(A));
}

후기

처음 문제를 보았을 때에는 감이 안 오는 문제였습니다. 하지만 이진수를 쭉 써보고, 규칙을 찾는 과정이 흥미로웠으며, 별다른 기능을 사용하지 않고 문제를 풀 수 있기에 사고력을 기르고 싶어하는 사람에게 추천하고 싶은 문제입니다.