[BOJ] 1019번: 책 페이지

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

N이 10억으로 애매한 값이라 크긴 크지만 N = 천만, 이천만, 삼천만, .. 등에 대해 미리 계산을 해뒀다고 치면 그냥 1부터 N까지 for문 돌면서 직접 계산하는 방식으로도 시간 내에 해결이 가능할 것 같긴 합니다. 그런데 그것보다는 조금 더 그럴싸하게 풀고 싶으니 구간을 적절하게 나눠봅시다. 나누는 방법은 사람마다 다르겠지만 저는 아래와 같이 나눴습니다.

1~42013

-> 1~9999

-> 10000~19999

-> 20000~29999

-> 30000~39999

-> 40000~40999

-> 41000~41999

-> 42000~42009

-> 42010~42010

-> 42011~42011

-> 42012~42012

-> 42013~42013

이렇게 하면 각 구간 고정된 prefix와 변하는 부분의 size으로 표현할 수 있습니다. 예를 들어 41000~41999의 경우 prefix는 41, 변하는 부분의 size는 3(1000으로 쓸 수도 있겠지만 저는 지수를 이용해 3이라고 표현했습니다.)

prefix가 0이 아닌 경우, 변하는 부분에서 0~9는 균등하게 sz*10^(sz-1)번씩 등장하고 prefix는 prefix의 각 글자가 10^(sz)번 등장합니다.

prefix가 0인 경우가 조금 까다로운데, 0000~9999와 같은 형태면 0~9가 균등하게 등장하지만 1~9999에서는 그렇지 않기 떄문입니다. 이를 쉽게 해결할 수 있는 방법으로는 0000~9999에서 1,2,3,...,9가 등장하는 횟수 = 1~9999에서 1,2,3,...,9가 등장하는 횟수임을 이용해 숫자의 갯수를 1~9가 등장하는 횟수로 빼주면 0이 몇번 등장하는지 알 수 있습니다.

한 두개 빼먹기 딱 좋은 문제인데 다행히 한번에 바로 맞았습니다.

https://github.com/blisstoner/BOJ/blob/master/1019.cpp