백준 1019 (C++) 책 페이지

최초 업로드: 2025-08-09 14:01:07

최근 수정 시간: 2025-08-09 14:01:39

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] 책 페이지

[문제 링크](https://www.acmicpc.net/problem/1019)

## 문제 설명

지민이는 전체 페이지의 수가 N인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 N 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자.

## 입력

첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

## 출력

첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다.

## 풀이
#### 파일 입출력으로 미리 1000만 단위로 계산해놓고, 그 사이는 브루트포스로 탐색해주었습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll cnt[10];
ll gap = 1e7;
ll pre[100][10] = {
    {5888896, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001},
    {7000001, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999},
    {16999999, 17000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 26999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 17000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 17000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 17000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000},
    {7000000, 17000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000},
    {7000000, 17000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000},
    {7000000, 17000000, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000},
    {7000000, 17000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001},
    {7000001, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999},
    {16999999, 7000001, 17000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 16999999, 17000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 26999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 17000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 17000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 17000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000},
    {7000000, 7000000, 17000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000},
    {7000000, 7000000, 17000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000},
    {7000000, 7000000, 17000000, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001},
    {7000001, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999},
    {16999999, 7000001, 7000000, 17000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 16999999, 7000001, 17000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 16999999, 17000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 26999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 17000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 17000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 17000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000},
    {7000000, 7000000, 7000000, 17000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000},
    {7000000, 7000000, 7000000, 17000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001},
    {7000001, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 16999999},
    {16999999, 7000001, 7000000, 7000000, 17000000, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 16999999, 7000001, 7000000, 17000000, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 16999999, 7000001, 17000000, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 16999999, 17000001, 7000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 26999999, 7000001, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 17000000, 16999999, 7000001, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 17000000, 7000000, 16999999, 7000001, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 17000000, 7000000, 7000000, 16999999, 7000001, 7000000},
    {7000000, 7000000, 7000000, 7000000, 17000000, 7000000, 7000000, 7000000, 16999999, 7000001},
    {7000001, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 16999999},
    {16999999, 7000001, 7000000, 7000000, 7000000, 17000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 16999999, 7000001, 7000000, 7000000, 17000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 16999999, 7000001, 7000000, 17000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 16999999, 7000001, 17000000, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 16999999, 17000001, 7000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 26999999, 7000001, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 17000000, 16999999, 7000001, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 17000000, 7000000, 16999999, 7000001, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 17000000, 7000000, 7000000, 16999999, 7000001},
    {7000001, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 16999999},
    {16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 17000000, 7000000, 7000000, 7000000},
    {7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 17000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 17000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 17000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 17000000, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 17000001, 7000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 26999999, 7000001, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 17000000, 16999999, 7000001, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 17000000, 7000000, 16999999, 7000001},
    {7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 16999999},
    {16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 17000000, 7000000, 7000000},
    {7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 17000000, 7000000, 7000000},
    {7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 17000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 17000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 17000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 17000000, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 17000001, 7000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 26999999, 7000001, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 17000000, 16999999, 7000001},
    {7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 16999999},
    {16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 17000000, 7000000},
    {7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 17000000, 7000000},
    {7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 17000000, 7000000},
    {7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 17000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 17000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 17000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 17000000, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 17000001, 7000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 26999999, 7000001},
    {7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 17000000},
    {16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 17000000},
    {7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 17000000},
    {7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 17000000},
    {7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 7000000, 17000000},
    {7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 7000000, 17000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 7000000, 17000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 7000000, 17000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 7000001, 17000000},
    {7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 16999999, 17000001},
    {7000002, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 26999998},
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;

ll cur=1;
 for(int i=0;cur+gap-1<=n;i++) {
 for(int j=0;j<10;j++) cnt[j] += pre[i][j];
 cur += gap;
 }
 for(;cur<=n;cur++) {
 string s = to_string(cur);
 for(char ch : s) cnt[ch-'0']++;
 }
 for(int i=0;i<10;i++) cout << cnt[i] << ' ';
}
```