BOJ 12755 - 수면 장애

링크: https://www.acmicpc.net/problem/12755

2016 전북대학교 프로그래밍 경진대회 A번

비슷한 문제로는 BOJ 1748 - 수 이어 쓰기 1이 있는데, 거기에 조건을 하나 더 얹었다.

앞에서부터 \(N\)번째 자리에 있는 수를 출력하는 것이다.

1부터 \(N\)까지 전부 확인하는 건 시간적으로도 메모리적으로도 무리다. 따라서 탐색 범위를 좁힐 필요가 있는데 이 문제에서는 자리수별로 인덱스를 자르면 좀 낫다.

1자리 수는 1부터 9까지 9개가 있으며, 전부 이어 붙이면 길이가 9이다.

2자리 수는 10부터 99까지 90(=99-10+1)개가 있으며, 전부 이어 붙이면 길이가 180(=90*2)이다.

3자리 수는 100부터 999까지 900(=999-100+1)개가 있으며, 전부 이어 붙이면 길이가 2700(=900*3)이다.

...

위를 이용하면 \(N\)번째 자리는 몇 자리 숫자가 전개되던 상황인지 알 수 있다.

1자리 수는 1~9번째를 이루고 있고, 2자리 수는 10~189번째를 이루고 있다. (10번째부터 180개면 189번째까지.)

마찬가지로 3자리 수는 190~2889번째를 이루고 있다는 것을 알 수 있다. 

k자리 수들을 이루는 경계를 통해 \(N\)번째 자리가 몇 자리 수인지 알 수 있다.

예를 들어 \(N=15\)라면, \(9 \lt N \le 189\) 이므로 2자리 수이다.

이렇게 알아낸 자릿수를 \(d\)라고 하면, \(10^{d-1}\)로부터 몇 번째 자리인지로 문제를 탐색 범위를 줄일 수 있다.

3자리 수는 100부터 10010110210310410510.. 로 진행된다. d자리 수는 한 숫자가 d칸을 차지하므로, 알고 싶은 위치를 index라고 할 때 (index / d)가 숫자이다.
즉, 3자리 수들을 전개했을 때 (0, 1, 2번째라고 센다면) 앞에서부터 8번째 자리는 다음 숫자의 일부이다.

$$10^{d-1} + (index / d) = 10^{3-1} + (8 / 3) = 100 + 2 = 102$$

102에서 \(8 % 3\)인 1번째 숫자는 0이므로 답은 0이다.