백준 1019번: 책 페이지

백준 1019번: 책 페이지

1019번: 책 페이지

근래 풀었던 문제중에 제일 어려웠던 것 같다. 도무지 풀 방법이 생각나지 않아 구글링을 했다, 와 이걸 어떻게 생각해내는 것일까 라는 생각이 들었다. 책의 페이지까지 나오는 모든 숫자의 개수를 구하는 1줄짜리 간단한 문제이지만 페이지의 범위가 10억까지여서 1부터 N까지 하나하나 계산하다 보면 1억 계산당 1초여서 10억이면 10초가 걸리게 되는 문제가 되어버린다. 그러니 여기서 규칙을 찾고 그 규칙을 코드화하면 된다.

 

규칙이란 것이 생각보다 어려운데 한번에 이해를 못해서 여러 글을 여러번 읽어봐야했다.

1부터 N까지 페이지를 보지말고 A부터 B까지의 페이지를 보자고 한다.

A = 10

B = 39

라고 가정하자

 

여기서 일의자리 숫자의 개수를 세자면

10 11 12 13 14 15 16 17 18 19

20 21 22 23 24 25 26 27 28 29

30 31 32 33 34 35 36 37 38 39

 

일의 자리 숫자만 3개씩 나오는 것이다.

이 3개라는 결과값은 일의자리를 제외한 나머지 숫자들을 빼서 1을 더한 값이다.

39와 10의 숫자에서 일의자리를 제외한 3 - 1 = 2 에서 2 + 1을 하여 3이 나온것이다.

 

그렇다면 나머지 자릿수도 똑같이 세면 될까라고 생각하지만 그렇지 않다.

만약 10과 39가 일의자리를 제외한 백의자리, 십의자리의 숫자라고 가정한다면

10 뒤에 일의자리가 0~9까지 있을 수 있고 마찬가지로 39 뒤에 일의자리가 0~9까지 있을 수 있다.

자리수가 올라갈수록 10배씩 많아질 것이다.

그래서 한 자릿수의 카운트가 끝나고나면 10배씩 양이 늘어난다는 점을 놓쳐서는 안된다.

 

단, 이 결과를 도출해내는데 조건이 있다. A의 일의자리는 0이고 B의 일의자리는 9일 경우에만 나타나는 결과이다.

따라서 A와 B의 일의자리가 위와 같지 않은 경우, A는 1을 더해주면서 0을 만들고

B는 1을 빼면서 9를 만들어주어야한다. 이때 더하고 뺄때 만들어지는 숫자의 각 자릿수의 숫자를 다 카운트해 정답에 포함시켜야한다.

 

 

더 자세한 설명은 이 페이지에서 확인하면 좋다.

https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1019

Baekjoon Online Judge 1019번 풀이

 

#include<iostream>
#include<cstring>
using namespace std;
long long count[10];
void calc(long long n, long long point){
    while(n > 0){
        count[n % 10] += point;
        n /= 10;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    long long n;
    long long start = 1;
    long long end;
    long long point = 1;
    memset(count, 0, sizeof(count));
    cin >> n;
    end = n;
    while(end >= start){
        while(start % 10 != 0 && start <= end){
            calc(start, point);
            start++;
        }
        if(start > end) break;
        while(end % 10 != 9 && start <= end){
            calc(end, point);
            end--;
        }
        long long rescalc = end/10 - start/10 + 1;
        for(int i = 0; i < 10; i++){
            count[i] += (point * rescalc);
        }
        start /= 10;
        end /= 10;
        point *= 10LL;
    }
    for(int i = 0; i < 10; i++){
        cout << count[i] << " ";
    }

    return 0;
}