[백준 1019] 책 페이지

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

 

1 ~ N 까지 수가 몇번이나 등장하는지 세는 문제

 

N의 자릿수가 올라가는 10의 계승마다 규칙을 찾는다. 0의 갯수가 자릿수마다 바뀌므로 규칙을 찾아보았다.

0의 갯수를 세기 편하게 자릿수가 1자리일땐 0 ~ 9, 2자리일땐 00 ~ 99 등으로 계산했다

규칙을 찾아보면 아래와 같다

 

자릿수	0의 갯수
1	1개(0)
2	1의자릿수(1개) + 10의자릿수(10개, 00 ~ 09지만 앞에서 00의 1의자리 0을 세었음) = 11개
3	1의자릿수 1개 + 10의자릿수 10개 + 100의자릿수 100개 = 111개
...
N	(int) 1.111111111 * 10의 N승

 

0의 갯수를 위 처럼 구하고 나머지 1 ~ 9의 개수는 몇번씩 세다보면 아래 표 처럼 된다

자릿수	1 ~ 9까지 등장하는 수의 갯수
1	1
2	20(1의 자릿수 10개, 10의자릿수 10개)
3	300(1의 자릿수 100개, 10의 자릿수 100개, 100의 자릿수 100개)
...
9	900000000
10	10000000000

 

위 값을 arr배열에 저장한다.

계산할 때는 제일 높은 자릿수부터 제일 낮은 자릿수까지 수의 개수를 센다

 

ex)

32547의 경우

1만자리(k)의 맨 앞자리수를 계산해 0부터 9까지 수가 몇 번 반복되는지 센다(변수 r = 3)

00000 ... 09999, 10000 ... 19999, 20000 ... 29999 ->  0000 ~ 9999가 r번 반복함. 0000 ~ 9999의 각 자릿수는 4000개이므로 4000 * 3 = 12000씩 카운팅된다.

이후 k 자리의 숫자에서 0, 1, 2가 k개씩 더 나오니 각각 k씩 더해준다. 3은 2547번 등장하니 n % k를 통해

나머지 + 1(30000 때문에) 만큼 더해준다.

그리고 남은 나머지를 이용해 자릿수 nk값이 0보다 작아질 때 까지 반복 한다

 

그리고 위 계산에서 누적된 0의 갯수를 다시 빼준다.(코드에서는 계산 전에 미리 뺏다)

 

#include <iostream>
#include "cmath"

#define ll long long
using namespace std;
int N;
ll arr[11], res[10];
void getPart();
void calc(ll n);
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;
    getPart();
    calc(N);

    for(ll r : res) {
        cout << r << ' ';
    }
}
void getPart() {
    for(int i = 1; i <= 10; i++) {   // 자릿수
        ll k = (ll) pow(10, i - 1) * i;
        arr[i] = k;
    }
}
void calc(ll n) {
    int nk = (int) log10(n);
    double t = 1.11111111111111111;
    res[0] -= (int) (t * pow(10, nk));  // 자릿수에 맞춰 0의 갯수 빼줌
    while(nk >= 0) {
        ll k = (ll) pow(10, nk);
        ll r = (n / k) % 10; // 자리수
        for(int i = 0; i < 10 && r != 0; i++) {
            res[i] += arr[nk] * r;
        }
        for(int i = 0; i < r; i++) {
            res[i] += k;
        }
        ll remain = n % k;
        res[r] += remain + 1;
        nk--;
    }
}