그냥 0~9가 페이지에 몇번 등장하는지 카운팅하라는 단순한 문제이다.
단순하게 생각해서 abcde 이렇게 다섯자리 수가 있다고 생각하자.
이걸 다섯개 구간으로 나눠서 카운팅할건데 0~a0000, a0000~ab000, ab000~abc00, abc00~abcd0, abcd0~abcde
이렇게 나눌 것이다.
이렇게 하는 이유는 자릿수가 하나 결정돼있으면 훨씬 세기 편해서이다.
0~a0000을 보면, 1부터 9까지 보면서 숫자가 a보다 작으면 10의3승*a*4 + 10의4승 만큼 숫자가 나오고, a보다 크면 10의3승*a*4 이렇게 나온다. 그냥 카운팅이니 경우의 수 따지기를 잘 해보면 된다.
이를 일반화 해보면 10^(digit-1)*a*digit+10^digit 이런식이다.
그리고 0은 1부터 N까지 숫자 구분없이 나오는 숫자의 전체 개수에서 1~9 개수를 빼주면 된다.
0도 위에서 한대로 해버리면 00123 이런 것도 0 두개를 카운팅해버리기 때문에 따로 처리해준다.
#include<stdio.h>
#include<stack>
#include<algorithm>
#include<math.h>
using namespace std;
long long N,M;
int digitnum;
long long ans[10] = {0,0,0,0,0,0,0,0,0,0};
stack<int> digits;
int main()
{
scanf("%lld",&N);
M = N;
while(N>0)
{
digitnum++;
digits.push(N%10);
N/=10;
}
long long all = (M - pow(10,digitnum-1)+1)*digitnum;
for(int i=1;i<=digitnum-1;i++)
{
all += i*9*pow(10,i-1);
}
while(digitnum>0)
{
int x = digits.top();
digits.pop();
for(int i=1;i<=9;i++)
{
if(digitnum>1) ans[i] += x*pow(10,digitnum-2)*(digitnum-1);
if(i<x) ans[i] += pow(10,digitnum-1);
}
M -= x*pow(10,digitnum-1);
ans[x]+=M+1;
digitnum--;
}
for(int i=1;i<=9;i++) all -= ans[i];
ans[0] = all;
for(int i=0;i<10;i++) printf("%lld ",ans[i]);
}전체 코드이다.
