[백준] 1019 - 책 페이지 (c++)

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

 

문제 요약

1부터 N까지 수에서 0~9가 몇 번 등장하는지 출력해라

 

풀이 (log10(N))

• 수학

Naive한 방법으로 시도하면 당연히 시간초과가 나게 된다. 문제를 좀 바꿔서 풀 수 있는데 각 자리마다 개수를 구하는 것이다. a~b에서 0~9가 몇 번 등장하는지 구해보자 a의 1의자리를 0으로 맞추고 b의 1의자리를 9로 맞추면 1~9가 각각 (b/10-a/10+1)번 등장한다. 1의 자리를 구한 다음에는 a/=10,b/=10를 해서 자를 하나 올려주고 똑같이 반복해주면 된다. 대신 (b/10-a/10+1)에 pow(10,자리)를 곱해줘야 한다. 1의자리를 맞추는 과정에서 a>b가 되면 안되기 때문에 조건문으로 a>b가 되면 반복을 종료해주면 된다.

 

구현은 재귀로 했다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll cnt[10];

void f(int a,int m) {
    while(a) cnt[a%10]+=m,a/=10;
}

void c(ll a,ll b,int m) {
    while(a%10&&a<=b)
        f(a,m),a++;
    if(a>b)return;
    while(b%10<9)
        f(b,m),b--;
    for(int i=0;i<10;i++)
        cnt[i]+=(b/10-a/10+1)*m;
    c(a/10,b/10,m*10);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;cin>>n;
    c(1,n,1);
    for(int x:cnt)
        cout<<x<<' ';
}