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이 몇번 등장하는지 알 수 있습니다.
한 두개 빼먹기 딱 좋은 문제인데 다행히 한번에 바로 맞았습니다.
'알고리즘 > 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 |