[백준 1019] 책 페이지

 

 구현 문제이다. N이 1,000,000,000까지 들어올 수 있기 때문에 선형 시간 알고리즘으로도 시간 초과가 나고, 규칙을 찾아야 한다. 

 적당히 작은 숫자를 두고 생각하다 보니, 나는 각 자릿수마다 등장하는 숫자를 카운트 해주는 방법이 가장 먼저 떠올라서 그 방법으로 풀었다. 

 

 특정 자릿수에 0~9가 몇 번 나타나는가를 생각하기 위해, 나는 자릿수를 기준으로 숫자들을 세 경우로 나누어 생각했다. 간단하게 N이 555인 경우, 십의 자리에 등장한 숫자들을 세는 것으로 예를 들면 다음과 같다.

 

1. 더 높은 자리에 위치한 수들이 아직 기존 수에 미치지 못하는 경우. 예시에서는 000~499이다. 이 경우는 더 낮은 자리에 나타날 수 있는 모든 경우 * 높은 자리에 위치할 수 있는 모든 경우만큼 0~9가 나타난다. 이게 글로 써두니까 조금 애매한데, 아래와 같이 생각하는 것이다.

 

 백의 자리에 나타날 수 있는 것은 0~4고, 일의 자리에 나타날 수 있는 것은 0~9다. 두 구간을 조합해서 나올 수 있는 경우의 수는 50이고, 가운데 십의 자리에는 0~9까지 모두 들어갈 수 있으므로 0~9까지 등장 횟수를 50 증가시킨다.

 이때 주의할 것이 있는데, 바로 앞자리가 모두 0만 나타나고, 탐색 중인 자리에도 0이 나타나는 경우를 제외해주어야 한다. 예를 들면 009 같은 경우인데, 이런 경우에는 실제 문제 의도상으로는 단순히 9이기 때문에 십의 자리에 0으로 나타난 것으로 간주하지 않는다. 그래서 나는 마지막에 0 등장 횟수에서 더 낮은 자리에 등장할 수 있는 경우의 수를 한 번 빼주었다. 555로 계속 예를 들자면 00[0...9] 케이스 때문에 반영된 십의 자리 0 등장 횟수를 빼주는 꼴이 되는 것이다.

 

2. 더 높은 자리에 위치한 수는 기존 수와 같고, 현재 탐색 중인 자릿수가 아직 기존 수에 미치지 못하는 경우. 예시에서는 500~549이다. 이 경우도 쉽게 생각할 수 있는데, 더 낮은 자리에 나타날 수 있는 모든 경우만큼 0~현재 자릿수-1까지 각각 출현한다. 십의 자리가 0일 때 일의 자리 0..9, 십의 자리가 1일 때 일의 자리 0..9, ... 와 같은 식으로 생각하면 된다.

 이 때도 주의할 것이 하나 있는데, 탐색 중인 자릿수가 가장 큰 자리일 경우다. 이 때는 탐색 중인 자리에 0이 오는 경우는 고려해서는 안된다. 나는 그래서 위와 마찬가지로 더 낮은 자리에 나타날 수 있는 모든 경우의 수를 한 번 빼주는 것으로 처리했다. 예시로 설명하자면, 555에 대해 백의 자리를 탐색할 때, 백의 자리에 0이 오는 경우를 빼준 것이다.

 

3. 현재 탐색 중인 자릿수까지는 기존 수와 같지만, 전체 수가 아직 기존 수에 미치지 못하는 경우. 예시에서는 550~555이다. 이건 더 낮은 자리에 나타날 수 있는 남은 경우만큼 현재 탐색 중인 자릿수가 출현하는 것으로 생각할 수 있다. 모듈러 연산으로 쉽게 구할 수 있다. 여기서는 5의 출현 횟수가 0..5에 해당하는 6회 증가할 것이다.

 

 

 이제 각 자릿 수마다 위 세 구간으로 나누어 올 수 있는 0~9 개수를 카운트 해주면 결과적으로 출현하는 모든 0~9의 갯수를 알 수 있게 된다.

 

 글로 풀어적긴 꽤 난해한 것 같다. 사람마다 숫자나 수열에서 먼저 찾아내는 패턴이 다르다 보니, 그냥 직관적으로 떠오른 걸 구현하는 게 편해 보이는 문제. 

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> numVector;
    vector<long long> result(10, 0);
    int num = n;
    while(num>0) {
        numVector.push_back(num%10);
        num/=10;
    }

    for(int i=0; i<numVector.size(); i++) {
        long long prev = 10;
        for(int j=0; j<i; j++) prev *= 10;
        long long subs = prev/10;
        prev = n/prev;

        if(prev>0) {
            long long baseSum = prev * subs;
            // 0~prev-1   [0~9]   0~아래 최대
            for(int j=0; j<10; j++) {
                result[j] += baseSum;
            }
            //앞자리 0으로 채워지고, 지금 자리도 0인 경우 
            result[0] -= subs;
        }

        //prev  [0~자리에 위치한 수 -1]  0~아래 최대
        for(int j=0; j<numVector[i]; j++) {
            result[j] += subs;
        }
        if(i==numVector.size()-1) {
            //탐색 중인 자리가 제일 앞자리일 때 0 갯수 카운트 x
            result[0] -= subs;
        }

        // prev [자리 위치 수] 0~아래 최대
        result[numVector[i]] += n%subs+1;
    }

    for(int res: result) {
        cout << res << " ";
    }

}