백준: Class 6 - 1019

</br> 클래스 6 계속
</br>

1019: 책 페이지

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

#include <bits/stdc++.h>

using namespace std;

int nums[10];

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

    int n;
    cin >> n;
    for(int i = 0; i < 10; i++){
        nums[i] = 0;
    }
    nums[0] = -1;

    for(int i = 0; i <= n % 10; i++){
        nums[i]++;
    }
    int k = n / 10;
    if( k > 0 ){
        for(int i = 0; i < 10; i++){
            nums[i] += k;
        }
        for(int i = 1; i < k; i++){
            int kk = i;
            while( kk ){
                nums[kk%10] += 10;
                kk /= 10;
            }

        }
        while( k ){
            nums[k%10] += n%10 + 1;
            k /= 10;
        }
    }

    for(int i = 0; i < 10; i++){
        cout << nums[i] << ' ';
    }
    cout << endl;
}

생각하는데 꽤 오래 걸렸다
만약 abcde라는 수라면, abcd와 e로 나누어서 볼 수 있다.

1. 일단 0~e까지가 한 번씩 나올 거다. 만약 n이 한 자리 수라면 0이 없으므로, 맨 처음에 nums[0] = -1로 초기화 해서 본다.
2. 그럼 이제 abcd만 신경 쓰면 된다.
3. abcd는 e+1번 나올 거다. 따라서 nums[a] += e+1, nums[b] += e+1, … 해준다.
4. 그럼 abcd-1은 0~9를 다 가지게 된다. 따라서 nums[i] += abcd-1을 해 준다.
5. 이제 abcd-1 자체도 계산해 주자. 0~9를 다 가지므로, 각각 10번씩 나온다.

예를 들어 보면

ex) 12345
1. 12340, 12341, 12342, 12343, 12344, 12345로 0~5까지가 한 번씩 나온다.
2. 이제 1234?만 신경 쓰자.
3. 1에서 봤듯이, 1234?는 5+1번 나온다. 따라서 nums[1] += 6, nums[2] += 6, nums[3] += 6, nums[4] += 6 해준다.
4. 그럼 이제 1233?이 남는다. 0~9가 1233번 나올 거다. 따라서 nums[i] += 1233을 한다.
5. 1?이 10번, 2?이 10번, ..., 1233?이 10번 나온다. 따라서, 각 자리수마다 10씩 더해 준다.

</br>

---

10억을 https://ideone.com/PbYoEg 에서 돌린 결과 1초 정도 나오는데, 시간 제한이 2초라서 맞기는 했다.
아마 어케 잘 짜면 재귀로 더 빠르게 구하는 게 될 거 같다
</br>