[BAE/<JOON> 문제풀이] 1019. 책 페이지

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

1019번: 책 페이지

 

핵심::

당연히 자리수 별로 나눠서 숫자 갯수를 구하는 규칙을 찾는 것이다.

 

입력의 크기가 10^9 이므로 자릿수 별로 나눠서 숫자를 세는 방법은 시간 제한을 만족시킬 수 없다.

 

풀이::

각 자릿수마다 0 ~ 9의 숫자들이 몇개씩 나오는지 체크하여 더하는 방식으로 구현하였다.

 

규칙은 다음과 같다. 

 

N 자리 수의 K번째 자릿수에 숫자 m의 등장 횟수 구하기 ( 1의 자리 K = 0 )

 

1. K자릿수를 기준으로 0 ~ (K - 1) (이하 back)구간과 (K + 1) ~ N (이하 front)구간으로 분할

 

2. 조건에 따라 계산

 i) K번째 숫자가 m을 초과할 경우

     sum += (front 구간 수( 합이 아닌 구간을 그대로 수로 바꾼 값 ) + 1) * 10 ^ K;

     

    -> 이미 해당 자릿수에서 나오는 모든 back구간 수들을 포함했으므로 별도의 back 구간수 계산이 필요없다.

        따라서 해당 자릿수에서 나오는 m의 갯수는

        ( [ 0 ~ (front 구간 수) ] 의 개수 ) * 10 ^ K 이다. 

        10 ^ K는 이하 자릿수에서 0 ~ 10 ^ K까지의 수가 반복되기 때문에 들어간 계산이다.

 

 ii) K번째 숫자가 m과 같을 경우

     sum += (front 구간 수) * 10 ^ K + (back 구간 수) + 1

 

     -> 0~(front 구간 수 - 1) 갯수의 m이 나오고 K번째 숫자가 m과 같을 때는 0 ~ (back 구간 수) 까지 m이 등장한다.

         따라서 해당 자릿수에서 나오는 m의 개수는

         ( [ 0 ~ (front 구간 수 - 1) ] 의 개수 ) * 10 ^ K + ( [ 0 ~ (back 구간 수) ])의 개수 + 1 이다.

 

 iii) K번째 숫자가 m 미만일 경우

     sum += (front 구간 수) * 10 ^ K

 

     -> 이 경우는 단순하게 K번째 자리에서 m이 단 한번도 나오지 않았으므로 (front 구간 수) - 1 까지만 계산하면 된다.

         따라서 해당 자릿수에서 나오는 m의 개수는

         ( [ 0 ~ (front 구간 수 - 1) ] 의 개수 ) * 10 ^ K 이다.

 

  3. 0 개수 세기

     0은 다른 숫자들과 다르게 가장 앞에 올 수 없다는 차이점이 있다. 따라서 0은 가장 첫째 자리에 오는 경우 수를 

     통채로 0으로 계산하며 2번째 자리부터는 (front 구간 수) - 1을 계산해준다. 

     왜냐하면 0 ~ ( front 구간 수 ) 까지가 K번째 자리에 올 수 있는 숫자인데 숫자 0인 경우 1 ~ ( front 구간 수) 로

     계산해야하기 때문이다. 

 

의견::

정형화된 알고리즘 문제보다 이런 수학 문제들이 풀었을 때 더 큰 카타르시스가 있는거 같다.

 

골드 1 문제 치고는 조금 쉬운 감이 있다.

 

코드::

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct bk { int front, back, x, p; };

int getcount(int n, const vector<bk>& var) {
    int sum = 0; 
    for (int i = 0; i < var.size(); i++) {
        int fxp = pow(10, var[i].p);
        if (var[i].x > n) { 
            // 현재 자리의 숫자가 정산하는 숫자를 포함하는 경우 
            sum += (var[i].front + 1) * fxp; 
        } 
        else if (var[i].x == n) { 
            // 현재 자리의 숫자가 정산하는 숫자와 같은 경우
            sum += var[i].front * fxp + (var[i].back + 1); 
        } 
        else if (var[i].x < n) { 
            // 현재 자리의 숫자가 정산하는 숫자를 포함하지 않는 경우 
            sum += var[i].front * fxp;
        } 
    }
    return sum;
}

int main() {
    /*int b = 2000;
    int cnt[10] = { 0, };
    for (int i = 1; i <= b; i++) {
        int pp = i;
        while (pp > 0) {
            cnt[pp % 10]++;
            pp /= 10;
        }   
        cout << i << " : ";
        for (int j = 0; j < 10; j++) {
             cout << cnt[j] << " ";
        }
        cout << "\n";
    }*/
    int n; cin >> n;
    vector<int> arr;
    int j = n; 
    while (j > 0) {
        arr.push_back(j % 10); 
        j /= 10; 
    }

    vector<bk> vl(arr.size());

    for (int i = 0; i < arr.size(); i++) {
        vl[i].p = i;
        vl[i].x = arr[i];
        int sum = 0;
        for (int j = i - 1; j >= 0; j--) {
            sum *= 10;
            sum += arr[j];
        }
        vl[i].back = sum;
        sum = 0;
        for (int j = arr.size() - 1; j >= i + 1; j--) {
            sum *= 10;
            sum += arr[j];
        }
        vl[i].front = sum;
    }

    vector<bk> vz(vl.begin(), vl.end() - 1);
    for (int i = 0; i < vz.size(); i++) {
        vz[i].front -= 1;
    }
    cout << getcount(0, vz) << " ";
    
    for (int i = 1; i <= 9; i++) {
        cout << getcount(i, vl) << " ";
    }

    return 0;
}