백준 1019번: 책 페이지 [C++]

작성일 | In
플래티넘 V 플래티넘 V

문제

책 페이지
1부터 $N$페이지 까지 있는 책에서 각 숫자가 모두 몇 번 나오는지 구하는 문제입니다.

풀이

각 자릿수별로 나눠서 구합니다.
전체적인 문제를 풀기 전에, 먼저 특수한 케이스 하나를 이용해 확장해 나가면 됩니다.

1 ~ 999꼴

예를 들어 보겠습니다. $1$페이지부터 $999$페이지까지 있는 책에서 1의 자리에서 나타나는 각 숫자의 개수를 모두 구해봅시다.
1의 자리에서는 0부터 9까지가 반복되는데, 이 반복횟수가 숫자0을 제외하고 $99+1$회임을 알 수 있습니다.
(01~09, 10~19, 20~29, ⋯ , 990~999로 100번 반복됩니다.)
어떤 페이지의 맨 앞은 0이 아니므로 0은 $99$회 나타납니다.

1의 자리가 아니라 다른 자리에서도 일반화하면 $10^i$번째 자리에서 1~9까지의 숫자가 나타나는 횟수는
$\lfloor N \div 10^{i+1} \rfloor \times 10^i$이고 0이 나타나는 횟수는 $\lfloor N \div 10^{i+1} - 1 \rfloor \times 10^i$임을 알 수 있습니다.

1 ~ $N$

예를 들어 보겠습니다. $N = 15798$이라고 해 봅시다.
$10^2$의 자리에서 각 숫자의 개수를 구해봅시다.
먼저 구하기 편하게 하기 위해 범위를 나눕니다.
1~14999와 15000~15798의 두 범위로 나눈 후, 각각에서 구하면 됩니다.
1~14999는 1 ~ 999꼴의 아이디어를 이용하면 $\lfloor 14999 \div 10^3 \rfloor \times 10^2 = 14 \times 10^2 = 1400$회 나타남을 알 수 있습니다.
(0의 경우 $\lfloor 14999 \div 10^3 - 1 \rfloor \times 10^2 = 1300$회 입니다.)

15700~15798의 경우 범위를 또 나눠서 생각합니다.
(15000~15099, 15100~15199, ⋯ , 15700~15798)
$10^2$번째 자리 숫자인 7을 제외하고 모두 $10^2$번 나타난다는 것을 알 수 있습니다.
7은 $(N\ mod\ 10^2) + 1$번 나온다는 것을 알 수 있습니다.

전체적으로 일반화해서, $10^m$자리 수 $N$이 주어졌을때, $i < m$인 $10^i$자리에 대해 각 수가 나타나는 횟수를 구하기 위해서
먼저 1~999꼴로 구할 수 있는 횟수를 구합니다.
$0$의 경우 $\lfloor N \div 10^{i+1} - 1 \rfloor \times 10^i$회
나머지의 경우 $\lfloor N \div 10^{i+1} \rfloor \times 10^i$회 입니다.

그리고 나서 나머지 횟수를 구해줍시다. $10^i$번째 자리 숫자를 $p$라 하면 $0 \leq q < p$인 숫자 $q$는
$\lfloor N \div 10^{i+1} \rfloor \times 10^i$회 나타납니다.
숫자 $p$는 $(N\ mod\ 10^i) + 1$번 나타납니다.

0을 예외처리 하지 않은 이유는 위의 1~999꼴에서 맨 앞에 0이 있는 경우를 이미 제외했기 때문입니다.
$i = m$인 경우에는 1~999꼴 부분을 제외하고 나머지 횟수만 구하면 됩니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
#define fastio() ios::sync_with_stdio(false); cin.tie(nullptr);
using namespace std;
using ll = long long;

ll cnt[10];


ll power(ll base, ll exp) {
    if (exp == 0) return 1;

    ll x = power(base, exp / 2);

    if (exp % 2 == 1) return x * x * base;
    else return x * x;
}


int main() {
    fastio();

    ll n;
    cin >> n;

    int maxDigit; // n의 최대 자릿수를 나타냅니다.
    for (int i = 0; i < 10; i++) {
        if (n / power(10, i) != 0) maxDigit = i;
    }

    for (int i = 0; i < maxDigit; i++) {
        ll temp = n / power(10, i+1) * power(10, i);

        cnt[0] += (n / power(10, i+1)-1) * power(10, i);
        for (int j = 1; j < 10; j++) {
            cnt[j] += temp;
        }


        ll nowDigit = n / power(10, i) % 10;
        for (int j = 0; j < nowDigit; j++) {
            cnt[j] += power(10, i);
        }
        cnt[nowDigit] += n % power(10, i) + 1;
    }
    // i == maxDigit인 경우 1~999꼴을 제외하고 구합니다.
    ll lastDigit = n / power(10, maxDigit) % 10;
    for (int j = 1; j < lastDigit; j++) {
        cnt[j] += power(10, maxDigit);
    }
    cnt[lastDigit] += n % power(10, maxDigit) + 1;


    for (int i = 0; i <= 9; i++) {
        cout << cnt[i] << ' ';
    }

    return 0;
}

여담

power함수를 직접 구현한 이유

power함수를 직접 구현한 이유는 별 다른건 아니고, 내장된 pow함수의 return값이 double이라 형변환 해주기 싫어서 그랬습니다.

테스트 케이스 몇개

제가 처음 풀 때는 숫자 0을 예외처리를 안해줘서 1000000000이 반례였습니다.

1
2
3
4
input:
1000000000
output:
788888898 900000001 900000000 900000000 900000000 900000000 900000000 900000000 900000000 900000000

또 0 예외처리를 잘못해서 100이 반례였습니다.
문제의 N이 작은 경우를 풀어주는 파이썬 코드를 작성해서 테스트 하면서 풀었습니다.

1
2
3
4
5
6
7
8
9
10
11
def getCounts(n: int) -> list[int]:
    count = [0 for _ in range(10)]

    for i in range(1, n + 1):
        for j in str(i):
            count[int(j)] += 1

    return count


print(getCounts(int(input())))

99, 100 등을 입력하면서 테스트 해 보세요! 도움이 되었길 바랍니다.

백준 1019번: 책 페이지 [C++]