[c++] 백준 1019 책 페이지

[문제]

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

1019번: 책 페이지

 

[풀이]

먼저 [A, B] 사이에 0~9가 등장한 횟수를 세는 것으로 생각해야 한다. A의 1의 자리가 0이고 B의 1의 자리가 9라면 그 사이에 0~9가 등장한 횟수는 공통적으로 B/10-A/10+1이 된다.

예를 들어, [22,  315] 라고 하면 처음 1의 자리가 0이 될 때까지 A를 증가시킨다. 이때의 값은 직접 계산해준다. 마찬가지로 B의 1의 자리가 9가 될 때까지 감소시켜주고, 그때까지의 횟수는 직접 계산한다. 

[30, 309]가 되면 30~309까지 1의 자리만 봤을 때, 0~9가 공통적으로 28번 등장한다. 30,31,32, ... ,39 까지 1의 자리 0~9가 10번, 40,41,42, ..., 49까지 10번, ... , 300, 301, 302, ... , 309까지 10번. 즉 B/10-A/10+1 = 30-3+1 = 28번이 공통적으로 등장하는 것이다. 

1에 자리에 등장하는 0~9를 모두 세었다면, A/10, B/10을 하고 자릿수를 10 곱해준다.

[3, 30]이 다시 1의 자리가 0이 될 때까지 증가, 1의 자리가 9가 될 때까지 감소시켜주며 이때의 값은 직접 계산한다. 이때, 실제로는 10의 자리수이므로 10씩 더해줘야 한다. 예를 들어, 3의 경우 실제로는 30~39까지 10의 자리인 3이 10번 등장한 것이다. (따라서 자릿수도 해당 함수에 전달해줘야 함.) 

[10, 29] 까지의 10의 자리에 등장한 0~9까지의 수를 세도록 한다. 마찬가지로 B/10-A/10+1은 2이고 2*10=20번만큼 0~9가 등장한 것을 알 수 있다. (사실상 [10,29]는 10*~19*까지 10의 자리 0~9가 10번, 20*~29*까지 10의 자리 0~9가 10번 등장한 것이다. -> 총 20번)

위의 과정을 반복하되, A가 B보다 커졌다면 계산 전에 위의 과정을 끝낸다.

 

[코드]

 

- 첫번째 시도

 

#include <iostream>
#include <string>

using namespace::std;

int main() {
    int array[10] = {0, };
    int n;
    cin >> n;
    //n=543212345
    for(int page=1; page<=n; page++){
        string num = to_string(page);
        for(int i=0; i<num.length(); i++){
            int idx = num[i]-'0';
            array[idx]++;
        }
    }

    for (int i:array){
        cout << i << " ";
    }

    return 0;
}

 

당연히 날 줄 알았던 시간초과...수학적 사고를 요구한 문제인데...너무 어려움.

 

- 풀이에 따른 코드

 

#include <iostream>
#include <string>

using namespace::std;

void calculate(int start, int answer[], int digit){
    while(start>0){
        int idx = start%10;
        answer[idx] += digit;
        start /= 10;
    }
}

int main() {
    int answer[10] = {0,};
    int page;
    cin >> page; //페이지 입력
    int start=1;
    int digit=1;
    while(start<=page){
        //1의 자리가 0이 될 때까지 start 증가
        while(start%10 != 0 && start<=page){
            calculate(start, answer, digit);
            start++;
        }

        if(start>page)
            break;

        //1의 자리가 9가 될 때까지 page 감소
        while(page%10 != 9 && start<=page){
            calculate(page, answer, digit);
            page--;
        }

        //0~9가 등장한 횟수 계산
        start = start/10;
        page = page/10;

        for(int i=0; i<10; i++){
            answer[i] += (page-start+1)*digit;
        }

        digit *= 10;

    }

    for (int i:answer){
        cout << i << " ";
    }

    return 0;
}