백준 #1019 책 페이지

한지민은 책을 좋아해서 도서관에서 근무한다.  그녀는 봄의 어느날 밤 책을 읽다가 문득 자신이 넘긴 책장에 있는 페이지에 얼마나 많은 숫자가 적혀있는지 궁금해졌다.  책의 페이지는 1 페이지부터 N 페이지까지 있다.  그녀가 읽은 책에는 과연 숫자가 몇개나 페이지에 적혀있는지 계산해보자.

 

 

원래 문제와는 조금 다르지만, 문득 한지민씨가 출연한 봄밤과 문제에 있는 지민이라는 이름이 겹쳐서 문제 내용을 바꾸어 보았습니다.  원래 문제는 아래의 링크에 있습니다.  난이도는 Gold I 문제입니다.

 

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

1019번: 책 페이지

이 문제를 브루트포스로 풀어도 큰 문제는 없어보입니다.  그러기에는 N 값이 10억으로 좀 큰가요?

숫자가 0으로 시작하지 않는다는 것만 제할 수 있다면, 사실 숫자 카운팅은 조금 더 쉬울겁니다.  0부터 999까지의 숫자를 생각한다면, 000, 001, 002, ..., 998, 999 식으로 0부터 9까지의 숫자가 똑같게 나옵니다.  저는 이 원리를 이용해서 문제를 풀었습니다.

숫자가 0으로 시작은 못하지만, 앞에 숫자가 있다면, 중간에는 얼마든지 0이 있을 수 있습니다.

 

예를 들어서 100 ~ 199까지 숫자에는 0의 갯수는 총 20개가 나타날거고, 9의 갯수도 총 20개가 나타날겁니다.  단 1의 갯수는 120개가 나타날겁니다.  100의 자리에 항상 붙박이처럼 1이 존재할테니까요.

 

이것을 이용해서 수학식을 구성해서 나름 모든 경우를 계산하지 않도록 하였습니다.

 

몇가지 입력의 예를 든다면 다음과 같습니다.

597
109 220 220 220 220 218 120 120 119 117 

7238
2143 3254 3193 3153 3144 3144 3144 2383 2144 2143 

987654321
780521262 891632373 891632364 891632284 891631584 891625584 891575584 891175584 888175584 868175584 

 

입력에 대한 출력값은 필요하신 분은 돌려서 올바르게 나오는지 확인용으로 사용해보세요.