수 이어 쓰기 2

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


풀이

문제를 해결하기 위해 몇 가지 과정을 거친다.
1. 수 이어 쓰기 1 문제에서 보듯 자리수가 차지하는 최대 자리 개수에는 규칙성이 있다.
이 규칙성을 이용해 자리수에 따라 차지하는 최대 자리의 누적된 개수(sum)가 k보다 작을 때까지 누적하고 그 때까지의 자리수(d)를 구한다.
그럼 k번째 자리 숫자가 몇의 자리인지를 알려주는 d와 k보다 작은 자리수가 차지하는 누적된 자리수(sum)를 알 수 있다.

2. k에서 sum을 빼어 k가 위치한 자리수의 0번째 부터 몇 번째인지 알아낸다.
여기서 -1을 해야하는데 십의 자리, 백의 자리 등 10, 100부터 시작하기 때문이다.

3. 이제 k에 d를 나누면 그 몫은 d의 자리의 몇 번째인지 알 수 있고 몫에 10^(d-1)을 더하면 k가 위치한 자리의 수를 알 수 있다.(tn)
그리고 k에 d를 나누고 나머지는 tn의 어느 자리인지 알려준다.(td)

4. 이제 td을 이용해 tn의 몇 번째 자리가 해답인지 출력한다.
그 전에 tn이 n보다 클 경우 k번째 자리 숫자가 없는 경우이므로 -1을 출력한다.