BOJ 1019 책 페이지

책 페이지
(http://boj.kr/1019)

전에 대충생각했다가 틀려서 묵혀놨는데, 새벽이라 집중이 잘 돼서 결국 풀었다.

푸는 방법은 여러가지가 있겠지만,
나는 일단 N보다 한 자리수 작은 것들을 먼저 셌다.
예를들어 N이 5자리 수라면, 4자리수에서 1~9까지의 숫자는 $4\times{10^3}$번 등장한다. (0은 따로 계산했다.)

그 뒤에, 현재 수를 본다. 예를들어 N이 1231라고 해보자.
그러면,
0XXX인 경우는 불가능하므로 넘어간다.
10XX인 경우는 1과 0이 $10^2$번 등장하고 모든 숫자가 $2\times{10^1}$번 등장한다.
11XX인 경우는 1과 1이 $10^2$번 등장하고 모든 숫자가 $2\times{10^1}$번 등장한다.
120X인 경우는 1과 2와 0이 $10^1$번 등장하고 모든 숫자가 $1\times{10^0}$번 등장한다.
121X인 경우는 1과 2와 1이 $10^1$번 등장하고 모든 숫자가 $1\times{10^0}$번 등장한다.
122X인 경우는 1과 2와 2이 $10^1$번 등장하고 모든 숫자가 $1\times{10^0}$번 등장한다.
1230인 경우는 1과 2와 3과 0이 $10^0$번 등장한다.
1231인 경우는 1과 2와 3과 1이 $10^0$번 등장한다.

사실 0을 계산하는게 제일 힘들었다...

#include <bits/stdc++.h>
 
using namespace std;
 
long long ans[10], d[10];
 
int main() {
    string str;
 
    cin >> str;
 
    long long cnt = 1;
    for (int i = 0;i < (int)str.length() - 2;++i)
        cnt *= 10;
    for (int i = 1;i < 10;++i) 
        ans[i] = (str.length() - 1) * cnt;
    d[0] = 1;
    for (int i = 1;i <= 9;++i)
        d[i] = d[i - 1] * 10;
    for (int i = 2;i <= (int)str.length() - 1;++i)
        ans[0] += 9 * (i - 1) * d[i - 2];
 
    vector<int> v;
    for (int i = 0;i < str.length();++i) {
        ans[str[i] - '0']++;
        for (int j = 0;j < str[i] - '0';++j) 
            if (!(i == 0 && j == 0)) {
                ans[j] += d[str.length() - i - 1];
                for (int t : v)
                    ans[t] += d[str.length() - i - 1];
                for (int k = 0;k < 10;++k) 
                    ans[k] += (str.length() - i - 1) * d[str.length() - i - 2];
            }
        v.push_back(str[i] - '0');
    }
 
    for (int i = 0;i < 10;++i)
        cout << ans[i] << ' ';
 
    return 0;
}