1019번

1019번 - 책 페이지

사실 다시 풀어봐야 할 문제 같다. 고민하다 결국 못 풀고, 백준 해설을 보고 이해하고 스스로 풀어봤다.

해설=> http://gooddaytocode.blogspot.kr/2016/05/boj.html

일단 각 자릿수 별로 계산을 한다는 아이디어가 정말 신기하고 놀라웠다.

그러기 위해서 시작점의 끝을 0, 끝나는 점의 끝을 9로 맞춰서 계산하기 간편하게 하는 스킬도 대단했다.

나는 떠올리지 못했을 해법인 거 같다..

그래서 풀이를 보고, 다시 풀어봤는데, 백준님은 시작점을 1로 놓고, 시작점을 증가시킨느 반면,

나는 시작점을 0으로 놓고 풀었다, 어차피 시작점의 끝을 0으로 맞춰야 하는데, 왜 1로 푸는걸까? 라는 생각을 하면서..

근데 풀다보니, 계속 틀린값이 나왔다..

그래서 천천히 왜 그런가를 예제를 돌려보며 생각했는데, 0부터 시작하다 보니, 0으로 비교, 00으로 비교, 000으로 비교..

이런식으로 계산이 되면서, , 중복되서 더해지는 오류가 발생하였다.

즉, 0 페이지가, 0일때 1번, 00일때 10번, 000일 때 100번 이런식으로 중복해서 더해졌다. 0페이지는 더해져서는 안되는 값인데!

그래서 그 값들을 모두 나중에 빼주니 정답을 구할 수 있었다.

<정답 코드>

#include<iostream>
 
using namespace std;
 
typedef long long ll;
ll cnt[10];
void make9(ll n, ll k)
{
    while (n>0)
    {
        cnt[n % 10] += k;
        n = n / 10;
    }
 
}
int main()
{
    ll n, head, k = 1;
    bool timeTofinish = false;
    scanf("%lld", &n);
 
    while (true)
    {
        while (n % 10 != 9 && n >= 0)
        {
            make9(n, k);
            n--;
        }
 
        if (n <= 0)
        {
            break;
        }
 
        head = n / 10;
 
        for (int i = 0; i <= 9; i++)
        {
            cnt[i] += ((head + 1) * k);
        }
 
        cnt[0] -= k;
 
        k *= 10;
        n = head;
    }
 
    
 
    for (int i = 0; i <= 9; i++)
    {
        printf("%lld ", cnt[i]);
    }
    puts("");
    return 0;
}