https://www.acmicpc.net/problem/1019
1019번: 책 페이지
첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다.
www.acmicpc.net
숫자 N이 주어졌을 때 1(첫 페이지)부터 N까지 쭉 순회하면서 등장한 숫자를 세는 건 당연히 안된다. 그 방법으로는 절대로 안된다는 걸 직관적으로 알려주기 위해 N의 상한이 10억이다...
그러면 당연히 숫자가 주어졌을 때 그 숫자만 보면서 답을 구할 수 있지 않을까라는 생각을 해봐야 한다.
필자가 생각한 방법은 주어진 숫자를 첫자리, 중간자리, 끝자리 이렇게 3개의 파트로 나누는 것이다.
예를 들어, 3516라는 숫자가 주어졌다고 하자. 그러면 첫자리는 3이고 중간자리는 51이고 끝자리는 6이다.
각 자리에 올 수 있는 0부터 9까지 숫자를 세어 누적해주는 것이다.
첫자리는 첫자리뒤에 있는 수+1 만큼 등장한 것이 보장된다.
3은 516+1 = 517번 등장한 것이다.
3000부터 3516는 516+1번이기 때문이다.
그리고 주의할 부분은 3뿐만 아니라 1,2도 1000번씩 등장한다는 점이다.
3000에 이르기 위해서는 1000~1999를 거쳤고, 2000에서 2999까지를 거쳤기 때문이다.
즉, 1부터 3미만의 숫자들은 곱하기 10^(현재 자리수, 이 경우엔 3)만큼씩 등장했다.
그 이외의 숫자는 첫자리에서 등장하지 않는다.
temp = int(n[1:]) <--- 뒷자리의 숫자를 찾기 위함.
ans[e] += temp+1 <--- 해당자리의 숫자는 temp+1만큼 추가
for j in range(1, e):
ans[j] += 10**(sz-1) <--- 1부터 3미만의 숫자들은 곱하기 10^(현재 자리수, 이 경우엔 3)만큼씩 등장
그리고 중간자리에 앞서 마지막 자리를 생각해보자. 이 경우엔 6가 된다.
3516까지 오기까지 6, 16, 26, ...이런식으로 거쳐왔을테고, 그렇다면 351+1번 등장했다는 걸 알 수 있다.
즉 첫자리를 처리한 것처럼, 마지막 자리 숫자를 떼어낸 숫자 (351) + 1이 6가 등장한 횟수가 된다.
그리고 첫자리 처리때와 마찬가지로 6미만의 숫자도 똑같이 351+1번 등장했다.
3516 바로 앞에 3515이 있었고, 이 3515도 5, 15, 25, ...이렇게 거쳐왔기 때문이다.
0은 351+1이 아닌 351번이다. 왜냐면 첫페이지는 항상 1이기 때문이다. 주의할 부분이 많다;
아직도 남은 부분이 있다. 아까 첫자리를 처리할 때는 3보다 큰 수는 생각하지 않았다. 왜냐하면 등장하지 않았기 때문이다.
하지만 마지막 자리는 다르다. 3516이 있었다면 3507이 있었다... 즉 6보다 큰 7,8,9는 350 + 1번 등장했다. 351+1이 아닌 350+1이다.
temp = int(n[:-1])
ans[0] += temp <--- "0은 351+1이 아닌 351번이다. 왜냐면 첫페이지는 항상 1이기 때문"
for j in range(1, e+1):
ans[j] += temp+1
for j in range(e+1, 9+1):
ans[j] += temp
중간자리보다 앞자리와 끝자리를 먼저 처리한 이유는 중간자리가 바로 위 2가지 처리의 합성으로 처리하기 때문이다.
3516에서 5와 1이 중간자리인데, 먼저 5의 자리 백자리를 보자.
이 자리에서 1은 몇번 나왔을까. 100부터 199까지 100번, 1100에서 1199까지 100번, 2100에서 2199까지 100번, 도합 300번이 되었다. 여기까지는 사실 1부터 9까지 같다. 0은 1000부터 1099, 그리고 2000~2199까지만 가능하므로 (3-1)*100=200번만 등장한다.
이제 여기서 0부터 4까지는 3000~3099, 3100~3199, ...까지의 100번씩을 추가해주어야 한다.
마지막으로 5는 16+1 번이 추가로 등장한다.
이제 정리하면 중간자리에는 1부터 9까지 앞에 있는 숫자(3) 곱하기 현재 자리수(100)만큼이 일단 등장하고, 0은 그 숫자보다 하나 적은 수 곱하기 자리수만큼이고, 해당 숫자보다 작은 수(0~4)는 자리수만큼을 더 추가해준다. 그리고 해당 자리에 있는 숫자(5)는 뒤에 있는 숫자16 + 1만큼 더 등장한다는 점을 알 수 있다.
temp1 = int(n[:i])
temp2 = int(n[i+1:])
ans[0] += (temp1-1)*(10**(sz-1-i)) <--- "0은 300번이 아닌 200번"
for j in range(1, 10):
ans[j] += temp1*(10**(sz-1-i)) <--- "도합 300번"
for j in range(e):
ans[j] += 10**(sz-1-i) <--- "해당 숫자보다 작은 수(0~4)는 자리수만큼을 더 추가"
ans[e] += temp2+1 <--- "마지막으로 5는 16+1 번이 추가로 등장"
차분히 하나하나 짚어서 생각해야 한다. 쉽지 않다고 생각한다.
<코드>
import sys
si = sys.stdin.readline
def main():
n = si()[:-1]
sz = len(n)
ans = [0 for _ in range(10)]
if sz == 1:
for i in range(int(n)+1):ans[i] += 1
ans[0] -= 1
print(*ans)
return
for i, e in enumerate(n):
e = int(e)
if i == sz-1:
temp = int(n[:-1])
ans[0] += temp
for j in range(1, e+1):ans[j] += temp+1
for j in range(e+1, 9+1):ans[j] += temp
elif not i:
temp = int(n[1:])
ans[e] += temp+1
for j in range(1, e):ans[j] += 10**(sz-1)
else:
temp1 = int(n[:i])
temp2 = int(n[i+1:])
ans[0] += (temp1-1)*(10**(sz-1-i))
for j in range(1, 10):ans[j] += temp1*(10**(sz-1-i))
for j in range(e):ans[j] += 10**(sz-1-i)
ans[e] += temp2+1
print(*ans)
if __name__ == '__main__':
main()
