[BOJ 백준] 9527번 : 1의 개수 세기 (C++)

[BOJ 백준] 9527번 : 1의 개수 세기 (C++)

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드
• 04. 마무리

---

01. 개요

출처

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

 

문제

 

입력

 

출력

 

예시

 

 

---

02. 접근 방식

 

요약

1. 입력 범위가 1~10^16 이므로, 모든 수를 검사하면, 시간 초과

2. 자릿수별(2의 배수)로 1의 개수를 저장해서 사용

3. 특정 값을 찾을 때, 자릿수별로 저장한 값을 계속해서 빼서, 1의 개수 구하기

 

과정

먼저, 가장 최악의 경우를 생각하면, a=1이고 b=10^16이 된다.

즉, 1~10^16까지 1의 개수를 구해야 하는데, 하나씩 탐색할 경우에는 최소 10^16번 진행해야 합니다.

그러므로, 시간 초과가 발생합니다.

 

이를 줄이기 위해서 0부터 1의 개수를 살펴보고, 반복되는 특징이 있는지 찾아보겠습니다.

먼저, 0부터 31까지의 수에 대한 2진수로 변환하면, 위 표와 같습니다.

 

2진수로 볼 때, 1자리와 2자리 수에 대해 비교해 보겠습니다.

2진수로 2자리의 수에서 1자리의 수에 있는 순서대로 다시 반복하고 앞에 1이 추가됩니다.

 

 2진수로 3자리의 수에서도 마찬가지로 2자리의 수에 있는 순서대로 다시 반복하고 앞에 1이 추가됩니다.

 

즉, 2진수로 [n자릿수의 경우 = 1 + (n-1) 자리 수의 경우]가 성립하게 됩니다.

이를 통해서 각 자리 수 별로 1의 개수와 (2^n-1)까지의 1의 총 개수를 미리 구할 수 있습니다.

 

이제, 미리 구한 1의 총 개수를 바탕으로 특정 수까지 1의 총 개수를 구해보겠습니다.

 

예시로 12까지 1의 총 개수를 구하면, 다음과 같습니다.

 

num = (12+1)을 대입하고, 이에 대한 자릿수를 먼저 구합니다.

num에 12가 아닌 13을 저장하는 이유는 처리해야 할 데이터는 0까지 포함시키기 때문입니다.

2의 배수(자릿수가 변경될 때)마다 첫 번째 자리를 제외하고는 모두 0으로 구성되어 있습니다.

이를 처리하기 위해, num에 1을 더한 값을 저장합니다.

 

12는 4자리 수이므로 그 이전인 3자리 수를 모두 제거합니다.

 

num(13)에서 이전에 처리한 8개를 제거하면, num=5가 됩니다.

 

이는 앞으로 처리할 데이터가 5개가 더 남았다는 의미가 됩니다.

num = 5이면, 2진수 2자리 수까지는 모두 포함하고 있다는 의미가 됩니다.

그래서, 2자리 수까지 1의 개수 총합을 더하고 앞에 1이 더해지지 않은 부분을 추가로 처리합니다.

 

4개를 추가로 처리했으므로, num = 1이 됩니다.

마지막으로 남은 num=1은 반드시 0이므로 추가 처리가 필요합니다.

데이터를 모두 처리했을 때(num=0), 탐색을 종료합니다.

 

여기서, 1에 대한 추가 처리는 (num을 뺀 횟수) * (이번에 처리할 데이터 수)의 값을 더하면 됩니다.

 

위 방식으로 b까지 1의 총 개수와 (a-1)까지 1의 총 개수를 구해서 빼면 정답을 얻을 수 있습니다.

 

주의점

숫자 0에 대한 처리를 하지 않으면, 너무 많은 조건문을 필요로 합니다.

하지만, 숫자 0에 대한 처리를 하면, 코드가 비교적 간결해집니다.

 

---

03. 정답 코드

// 골드 2 - 9527번 : 1의 개수 세기
// 작성자 : free4760(jeonghoe22)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// a <= x <= b
// a와 b는 1~10^16

// f(n) -> n자리 수에서 이진수를 만들 때, 1이 있는 경우의 수
// sum(n) -> f(1)+...f(n)의 합

// sum(n) = sum(n-1) + f(n)

using ll = long long;

struct Digit
{
    ll num = 0;
    ll each = 0;
    ll sum = 0;
};

vector<Digit> g_digits;

// b에 대한 기준으로 먼저 자릿수에 따른 1의 개수 먼저 구하기
void search(const ll B)
{
    g_digits.reserve(60);

    ll prev = 2;
    ll cur = 4;

    g_digits.push_back({1, 0, 0});
    g_digits.push_back({2, 1, 1});

    int digit = 2;

    while(cur <= (B * 4))
    {
        Digit createDigit;
        createDigit.each = (cur - prev) + g_digits[digit-1].sum;
        createDigit.sum = g_digits[digit-1].sum + createDigit.each;
        createDigit.num = cur;
        g_digits.push_back(createDigit);

        digit++;
        prev = cur;
        cur = cur << 1;
    }
}

// 해당 수에 대한 1의 개수 구하기
ll simulate(const ll in_num)
{
    ll num = in_num + 1;

    int digit = 0;
    ll count = 0;
    ll times = 0;
    while(num > 0)
    {
        // 자릿수 구하기
        if(g_digits[digit].num <= num)
        {
            digit++;
            continue;
        }
        // 처음으로 초과된 자릿수이므로 하나 제거
        digit--;

        num -= g_digits[digit].num;

        // 14 -> 처음 8개 제외
        // 7 -> 두 번째 4개 제외 (제일 앞에 1이 붙음)
        // 3 -> 세 번째 2개 제외 (제일 앞 두 글자에 1이 붙음)
        // 1 -> 네 번째 1개 제외 (제일 앞 세 글자에 1이 붙음)
        count += (g_digits[digit].num * times);

        // 이전 자리수에 대한 1의 개수를 더하기
        count += g_digits[digit].sum;

        // 자릿수 초기화
        digit = 0;
        times++;
    }
    return count;
}

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 두 자연수 A, B
    ll A, B;
    cin >> A >> B;

    search(B);
    ll result = simulate(B) - simulate(A-1);
    cout << result << "\n";
}

 

---

04. 마무리

처음에 숫자 0에 대한 처리를 하지 않아, 시간이 조금 더 걸렸던 문제였습니다.

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!