[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

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 1025번: 제곱수 찾기  (6) 2018.02.11
[BOJ] 1023번: 괄호 문자열  (2) 2018.02.11
[BOJ] 1020번: 디지털 카운터  (2) 2018.02.10
[BOJ] 1014번: 컨닝  (0) 2018.02.07
[BOJ] 1300번: K번째 수  (0) 2018.02.05
[BOJ] 6324번: URLs  (0) 2018.02.01
  Comments