BOJ 1019 책 페이지

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

1019번: 책 페이지

간만에 머리좀 굴릴만한 문제를 풀었다.

 

1 ~ N 까지의 숫자들에 0 ~ 9 의 숫자가 각각 몇번씩 등장하는지 계산하는 문제이다.

당연히 1부터 N까지 하나하나 확인할 수 없도록 만들어놓았다.

그러면 규칙을 찾아야 할텐데..

규칙을 찾을때는 역시 값이 작은 부분에서 손으로 노가다를 해보면 된다.

두자리수를 가지고 대충 감을 잡고, 세자리수에 적용을 해봐서 수정을 해가면서 식을 찾으면 된다.

아니 왜 세자리수인가요?? -> 가운데자리수 가 등장하는 제일 작은 숫자이기 때문이다.

두자리수로만 식을 세우면 가운데자리수에 대한 처리가 미흡할 수 있기 때문이다.

그 결과.. 식을 찾아내었다.

/*
        
        어떤 자리수에 대해서 0~9가 몇번 나올지 계산하는 방법.
        ex) abcdefg 7자리 숫자라고 가정.

        1000의자리의 위치(d의 위치)에 0~9가 몇번 나올지 계산해보자.

        1. 앞자리(abc)의 값이 000 ~ (abc - 1) 사이일 때
            - 뒷자리(efg)는 000~999까지, 총 10^(뒷자리 자리수)개가 가능하다.
            - 따라서 1000의 자리에 1~9는 (앞자리에 오는 값의 가지수) X (뒷자리에 오는 값의 가지수) 만큼 등장한다.
            - 즉 1000의 자리에 1~9는 abc * 10^(뒷자리 자리수) 만큼 등장한다.
            - 이때, 1000의 자리에 0이 오는 경우는 앞자리(abc)의 값이 0이면 안된다.
            - 따라서 1000의 자리에 0은 (abc - 1) * 10^(뒷자리 자리수) 만큼 등장한다.

        2. 앞자리(abc)의 값이 딱 abc 일 때
            2-1. 1000의 자리수에 0 ~ d-1 의 숫자가 오는 경우
                - 뒷자리(efg)에 가능한 가짓수의 조합은 10^(뒷자리 자리수) 개이다.
                - 따라서 0 ~ d-1 의 숫자는 10^(뒷자리 자리수)만큼 추가로 등장한다.
            2-2. 1000의 자리수에 d의 숫자가 오는 경우
                - 뒷자리(efg)에 가능한 가짓수의 조합은 000 ~ efg 이다.
                - 따라서 d는 efg + 1 만큼 추가로 등장한다.
            2-3. 1000의 자리수에 d+1 ~ 9 의 숫자가 오는 경우
                - 불가능하다.


        이것을 일반화하면,
        n의 자리에 0~9 가 몇번 등장하는지 계산할 수 있다.
        
        */

 

바로 일반화를 해서 뚝딱뚝딱 코드를 짜면 된다.

실제 코드는 몇줄 되지 않는다.

하지만, 접근까지의 난이도가 생각보다 높아서 티어가 높은 문제인 듯 하다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <cmath>

using namespace std;

typedef pair<int, int> ii;

typedef long long ll;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; cin >> n;

    // 0 부터 9 까지 몇번 나왔는지 저장할 배열
    vector<ll> vec(10, 0);
    int t = n;

    // 각 자리수를 저장할 배열
    vector<int> decimal;
    decimal.push_back(0);
    while (t > 0) {
        // 각 자리수 저장
        decimal.push_back(t % 10);
        t /= 10;
    }

    // 각 자리수에 대해서
    for (int i = 1; i < decimal.size(); i++) {

        // 자리수의 앞부분
        int front = n / (int)pow(10, i);

        // 자리수의 뒷부분
        int back = n % (int)pow(10, i - 1);

        /*
        
        어떤 자리수에 대해서 0~9가 몇번 나올지 계산하는 방법.
        ex) abcdefg 7자리 숫자라고 가정.

        1000의자리의 위치(d의 위치)에 0~9가 몇번 나올지 계산해보자.

        1. 앞자리(abc)의 값이 000 ~ (abc - 1) 사이일 때
            - 뒷자리(efg)는 000~999까지, 총 10^(뒷자리 자리수)개가 가능하다.
            - 따라서 1000의 자리에 1~9는 (앞자리에 오는 값의 가지수) X (뒷자리에 오는 값의 가지수) 만큼 등장한다.
            - 즉 1000의 자리에 1~9는 abc * 10^(뒷자리 자리수) 만큼 등장한다.
            - 이때, 1000의 자리에 0이 오는 경우는 앞자리(abc)의 값이 0이면 안된다.
            - 따라서 1000의 자리에 0은 (abc - 1) * 10^(뒷자리 자리수) 만큼 등장이다.

        2. 앞자리(abc)의 값이 딱 abc 일 때
            2-1. 1000의 자리수에 0 ~ d-1 의 숫자가 오는 경우
                - 뒷자리(efg)에 가능한 가짓수의 조합은 10^(뒷자리 자리수) 개이다.
                - 따라서 0 ~ d-1 의 숫자는 10^(뒷자리 자리수)만큼 추가로 등장한다.
            2-2. 1000의 자리수에 d의 숫자가 오는 경우
                - 뒷자리(efg)에 가능한 가짓수의 조합은 000 ~ efg 이다.
                - 따라서 d는 efg + 1 만큼 추가로 등장한다.
            2-3. 1000의 자리수에 d+1 ~ 9 의 숫자가 오는 경우
                - 불가능하다.


        이것을 일반화하면,
        n의 자리에 0~9 가 몇번 등장하는지 계산할 수 있다.
        
        */


        for (int j = 1; j <= 9; j++) {
            vec[j] += front * (ll)pow(10, i - 1);
        }
        vec[0] += (front - 1) * (ll)pow(10, i - 1);
        
        for (int j = 0; j < decimal[i]; j++) {
            vec[j] += (ll)pow(10, i - 1);
        }
        vec[decimal[i]] += back + 1;
    }
    for (int i = 0; i < 10; i++) {
        cout << vec[i] << " ";
    }

    return 0;
}