[BOJ] 1019. 책 페이지

책 페이지

클릭시 이동합니다.

어떻게 풀까?

규칙을 찾으면 생각보다 간단하게 풀 수 있습니다!

간단하게 2834 라는 수를 생각해봅시다!

우선, 가장 큰 2천이라는 수를 봅시다

2천이라는 수 전에는

0~999라는 수가 있었을 것입니다.

그리고 1000~1999까지의 수가 있었겠죠!

엇! 이거.. 왠지 0~999까지가 반복되는 느낌이 있습니다.

그렇다면, 0~999까지 등장하는 0~9의 수를 세면 될 것 같습니다.

편의상 1도 001이라고 생각하겠습니다! (1001 같은 경우 때문이죠!)

잘 생각해보면, 모든 수가 1의 자리에서 100번, 10의 자리에서 100번, 100의 자리에서 100번씩 등장하는 것을 알 수 있습니다!

(즉, 0도 300번, 1도 300번, 2도 300번, 3도 300번, 4도 300번, 5도 300번, 6도 300번, 7도 300번, 8도 300번, 9도 300번 등장합니다!)

만약, 100의 자리였다면,

0~9 모든 숫자가 10의 자리에서 10번, 1의 자리에서 10번이 등장하겠죠!

그렇다면, 천의 자리가 0, 1 두 가지 경우에서 0~9는 총 300번씩 두번, 600번 나왔겠군요!

다만! 맨 앞자리에서는 문제가 있습니다.

편의상 1도 001로 했지만.. 그것은 1001 처럼 맨 앞자리가 0이 아닐때만 유효한 것입니다!

천의 자리가 0이었다면, 0001이라는 해괴한 숫자가 나오는 것이죠! 앞의 0 세개는 지워주어야 합니다...

이를 처리하려면 어떻게 해야할까요?

위에서 보면, 사라져야 하는 0의 개수를 대강 짐작할 수 있습니다.

10의 자리수는 이렇게 90개가 나오죠!

0010 ~ 0099

사라져야하는 0의 수는 앞의 2개 * 90개 인거죠!

100의 자리수는

0100 ~ 0999 로 900개 입니다!

사라져야하는 0의 수는 앞의 0 1개 * 900개 입니다!

digit은 자리수라고 하겠습니다! 예로, 1000의 digit은 3 입니다!

그렇다면, 식을 일반화 하면 아래 식과 같습니다.

다만, 1의 자리에서는 000 0을 제외하고 생각했기 때문에, digit을 한번 더 빼주는 것이 필요합니다!

다시한번 정리해드리면, 위에서 구한 식은 앞자리가 0일 때, 사라져야할 0의 개수 입니다!

이제 위를 0의 개수에서 빼고 시작하면, 모든 자리에서 동일한 계산식을 사용할 수 있습니다!

자, 이제 다시 위에서 예를 든 2834라는 식을 보겠습니다.

위에서 사라져야하는 0의 개수를 미리 빼주었기 때문에, 이제부터는 0001 부터 1999까지 등장하는 모든 숫자를 확인하면 됩니다!

우선, 001 부터 999 까지 등장하는 0~9의 모든 개수는 3천개입니다! (1000개의 수가 1의 자리, 10의 자리, 100의 자리에서 나타나기 때문이죠! 1000 * 3)

그리고, 0~9의 수가 균등하게 등장합니다! 따라서, 0~9의 모든 개수는 300개씩 등장하겠죠.

그리고, 맨 앞에 붙는 수는 0 001 ~ 0 999 이고, 1 001 ~ 1 999 이기 때문에, 0이 1000번, 1이 1000번이 추가로 등장할 것 입니다!

또한, 001 ~ 999가 2번 등장하기 때문에 총 600번씩 등장하겠네요!

 

이제 2를 볼 시간입니다.

우선, 2 000 ~ 2834 까지이기 때문에, 2는 835번 등장할 것입니다.

그리고 나머지 0~9의 등장 횟수는

000 ~ 834까지에서 0~9의 등장 횟수가 같겠죠!

천의 자리에서 해줄 수 있는 계산은 여기까지인 것입니다!

나머지는 이제 834에서의 계산을 위처럼 해주면 됩니다.

백의 자리에서 0~7의 개수는 0 00 ~ 0 99의 개수인 100개씩 나올 것이고,

백의 자리에서 8의 개수는 800 ~834 까지 35번 나올 것입니다.

백의 자리 0 ~ 7에서 등장하는 나머지 0~9의 개수는 00 ~99 까지 20번씩 등장하고, 0 ~ 7 까지 8번 반복되므로, 160 번 등장할 것입니다.

백의 자리 8에서 등장하는 나머지 0~9의 개수는 34에서 나오는 0~9의 개수와 같겠죠!

34는

십의 자리에서 0~2의 개수는 00 ~ 09의 개수인 10개씩 나올 것입니다.

3의 개수는 30~34까지 5개가 나올 것입니다.

십의 자리 0~2에서 등장하는 나머지 0~9의 개수는 0~9까지 1번씩 등장할 것입니다! 이것이 3번 반복되니까 총 3번 등장하겠군요!

나머지는 이제 4에서 등장하는 개수와 같고, 이는 1,2,3,4 가 되겠죠!

이를 다 더해 봅시다!

맨 처음 빼는 0의 개수는.. 

3*9 + 2*90 + 1*900 + 3 = 1110이겠군요.

0000~1999까지에서의 0~9의 개수는

600개씩이고,

추가적으로 0의 개수는 1000개, 1의 개수는 1000개, 2의 개수는 835개가 늘어납니다.

정리하면 

0	1	2	3	4	5	6	7	8	9
490	1600	1435	600	600	600	600	600	600	600

이렇게 될 것입니다.

이제 000 ~ 834를 확인해 봅시다.

0~7의 개수는 100개씩 늘어날 것입니다!

8의 개수는 35개가 늘어나겠죠!

그리고 나머지 0~9의 개수는 20개씩 * 8번 = 160개씩 늘어날 것입니다.

정리하면,

0	1	2	3	4	5	6	7	8	9
750	1860	1695	860	860	860	860	860	795	760

이제 34를 봅시다!

0~2의 개수는 10개씩 늘어날 것입니다.

3의 개수는 5개가 늘어나겠죠!

나머지 0~9의 개수는 1개 * 3번 = 3개씩 늘어날 것입니다.

나머지는 이제 4이기 때문에, 1,2,3,4가 하나씩 늘어나고 끝나겠죠!

마지막으로 정리하면...

0	1	2	3	4	5	6	7	8	9
763	1874	1709	869	864	863	863	863	798	763

이렇게 됩니다!

코드

//https://www.acmicpc.net/problem/1019
#pragma once
#include<cstdio>
 
long long pow(int cnt) {
    if (cnt < 0) return 0;
 
    if (cnt == 0) {
        return 1;
    }
 
    long long half = pow(cnt / 2);
    half *= half;
    if (cnt & 1) half *= 10;
    return half;
}
 
long long cnt[10];
 
int getDigit(long long n) {
    int res = 0;
    while (n) {
        res++;
        n /= 10;
    }
    return res-1;
}
int main() {
    long  long n;
    scanf("%lld\n", &n);
 
    int digit = getDigit(n);
    long long p = pow(digit);
 
    for (int i = 0; i < digit; i++) {
        cnt[0] -= (digit - i)*(pow(i+1)-pow(i));
    }
 
    cnt[0] -= digit;
 
    for (int i = digit; i > 0; i--) {
        int fr = n / p;
 
        for (int i = 0; i < fr; i++) {
            cnt[i] += p;
        }
        
        for (int i = 0; i < 10; i++) cnt[i] += fr*digit*pow(digit-1);
 
        n %= p;
 
        cnt[fr] += n + 1;
        digit--;
        p /= 10;
    }
 
    for (int i = 1; i <= n; i++) {
        cnt[i]++;
    }
    for (int i = 0; i < 10; i++) {
        printf("%d ", cnt[i]);
    }
    return 0;
}

여담

생각보다 햇갈렸습니다...

0의 개수 빼는거에서 시간을 많이 먹었네요!

규칙 자체는 찾기 힘든 편은 아니었던것 같습니다.