BOJ 1019. 책 페이지

 

문제 링크

 

문제 풀이

 이 문제는 $1$부터 $N \leq 10^9$까지의 수에서 등장하는 0 ~ 9의 개수를 출력하는 문제이다. 문제 자체는 쉽지만 TLE가 나지 않게 구현을 하려고 하면 조금 까다로운 문제이다.

 

 기본적인 아이디어는 $N$을 각 자리수에 따라 나누어 더블카운팅의 형식으로 세는 것이다. 예를 들어서 $N = 223$이라고 하면 $N$을 200, 20, 3으로 나누어서 0~199까지의 각 자리수의 개수, 0~19까지의 각 자리수의 개수, 0~3까지의 각 자리수의 개수를 따로 세주어 더하는 형식이다. 여기서 0~199까지의 각 자리수의 개수와 같은 경우는 또 0~99, 100~199로 나누어서 생각해볼 수 있다. 10의 거듭제곱 단위로 나뉘기 때문에 이에 대한 정보만 미리 저장해둔다면 빠른 시간 내에 처리할 수 있다.

 

 $b[i][j] := (0$부터 $10^{i} -1$까지 등장하는 $j\space(0\leq j\leq 9)$의 개수$)$로 정의를 해보자. 그런데 여기서 0을 제외하면 $j$가 어떤 수이든 등장횟수는 동일하므로 0을 제외하면 $b[i] := (0$부터$10^{i} -1$까지 등장하는 $j\space(1\leq j\leq 9)$의 개수$)$로 쓸 수 있다. 그리고 여기서 $b[i] = i\times 10^{i-1}$임을 쉽게 알 수 있다. 

 

 이를 이용하면 1~9까지의 수의 개수는 쉽게 구할 수 있다. $N = \overline{a_{m}a_{m-1}\cdot\cdot\cdot a_{1}}$이라고 할 때 등장하는 숫자 n의 개수를 수식으로 나타내면 다음과 같다.

$$\sum_{k=1}^m\left[a_{k}\times b[k-1]+\begin{cases}0 & a_k<n\\\overline{a_{k-1}a_{k-2}\cdot\cdot\cdot a_{1}} +1 & a_{k} = n\\10^{k-1} &a_k > n \end{cases}\right ]$$

 

 이제 0의 개수만 잘 고려해주면 된다. 0의 개수는 위에서 구한 식에서 $k = m$일 때 예외 처리를 잘해주기만 하면 된다. 이를 위해 새로운 $c[i]$을 정의해보자. $c[i] := (0$부터$10^{i}-1$까지 등장하는 $0$의 개수$)$. 일단 $c[1] = 1$임이 자명하다. 그리고 $c[i] = c[i-1] + 9\times b[i-1]$임을 쉽게 알 수 있다. 그래서 이를 이용해서 0부터  $N = \overline{a_{m}a_{m-1}\cdot\cdot\cdot a_{1}}$까지 등장하는 숫자 0의 개수를 수식으로 나타낼 수 있다.

$$(c[m-1] + a_{m}\times b[m-1]) + \sum_{k=1}^{m-1}\left[a_{k}\times b[k-1]+\begin{cases}\overline{a_{k-1}a_{k-2}\cdot\cdot\cdot a_{1}} +1 & a_{k} = 0\\10^{k-1} &a_k > 0 \end{cases}\right ]$$

 

 이제 이를 코드로 구현하면 된다.

 

 

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll b[11],c[11];
ll N;
int m = 0;
int NDigitNum[11];

void init(){
    //b[i] = 10^i-1 * i
    b[0] = 0;
    b[1] = 1;
    for(int i=2;i<=10;i++)  b[i] = (b[i-1]/(i-1)) * 10 * i;
    
    //c[i] := 0 ~ 10^i -1 까지 0 개수
    c[1] = 1;
    for(int i=2;i<=10;i++) c[i] = 9*b[i-1] + c[i-1];
    
    //split N by digit
    ll N_prime = N;
    while(N_prime>0){
        NDigitNum[m+1] = N_prime%10;
        N_prime /= 10;
        m++;
    }
}

void input(){
    cin>>N;
}

ll calcAmount(int n){
    ll ans = 0;
    if(n==0){
        if(N<10) return ans;
        
        for(int i=1;i<=m;i++){
            if(i==m) ans += c[i-1] + (NDigitNum[i]-1) * b[m-1];
            else{
                if(NDigitNum[i] == 0){
                    ll c = 1;
                    for(int j=1;j<i;j++){
                        ans += c * NDigitNum[j];
                        c *= 10;
                    }
                    ans ++;
                }
                else ans += (NDigitNum[i]) * b[i-1] + b[i]/i;
            }
        }
        
        ans --; //시작하는 0제외
    }
    else{
        for(int i=1;i<=m;i++){
            ans += NDigitNum[i] * b[i-1];
            if(NDigitNum[i]>n) ans += b[i]/i;
            if(NDigitNum[i] == n){
                ll c = 1;
                for(int j=1;j<i;j++){
                    ans += c * NDigitNum[j];
                    c *= 10;
                }
                ans ++;
            }
        }
    }
    
    return ans;
}

void solve(){
    for(int i=0;i<=9;i++){
        cout<<calcAmount(i)<<" ";
    }
}

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    input();
    init();
    solve();
}