10573 - 증가하는 수

234까지 증가하는 수의 개수를 이렇게 표현해봅시다.

000~234 사이에 증가하는 수의 개수.

그럼 각 자리마다 압축된 표현을 할 수 있습니다. 이게 무슨 말이냐면 3자리로 표현되는 모든 증가하는 수를 나열해봅시다.

000      ------
001
...         이 구간의 개수 = (10-0)개 = 10개
009      ------
011      ------
012
...         이 구간의 개수 = (10-1)개 = 9개
019      ------
022      ------
...         이 구간의 개수 = (10-2)개 = 8개
029      ------
088
...         이 구간의 개수 = (10-8)개 = 2개
089      ------
...
111      ------
...         이 구간의 개수 = (9+8+...+1)개 = 45개
199      ------

111~199 구간의 개수는 (X11~X19) +(X22~X29) + .. 이기 때문에 45개입니다.

이런식으로 각 구간의 개수를 XXX ~ YY9 와 같은 식으로 표현할 수있습니다.
123까지의 증가하는 수는 (0XX~099) + (1XX ~ 123) 입니다.

이렇게 센다면 "각 자리마다 압축된 표현"이 가능합니다. 예를 들어, 123 에서 1은 0XX~099 까지를 표현하고 있습니다. 즉, (해당 자리의 수-1) 까지의 모든 개수를 담고 있습니다. 그리고 이 개수는 자리수마다 다르겠죠.

각 자리수마다 X~9 구간에 있는 수의 개수는 다음과 같습니다. (왼쪽에서 오른쪽으로 X=0 -> 9 를 의미함)

1자리(X~9) : 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
2자리(XX~99) : 55, 45, 36, 28, 21, 15, 10, 6, 3, 1
3자리(XXX~999) : 220, 165, 120, 84, 56, 35, 20, 10, 4, 1

이런식으로 80자리를 모두 표현할 수 있습니다.

4457의 경우, 첫 자리의 4가 의미하는 건 (0XXX ~ 3999) 의 개수입니다. 여기에는 220 + 165 + 120 + 84 = 589개가 있습니다. 그리고 다음을 세어봐야하는데 다음은 4000 ~ 이 아닌 4444 ~ 임에 주의하시길 바랍니다.

즉, 두번째 자리의 4는 444 ~ 457 을 의미합니다. 이미 자리수가 같으므로 구간내(4XX~4XX)에서 나올 숫자는 없겠지요.

다음으로 세번째 자리는 44~57 를 의미합니다. 여기엔 (44~4X) = 6개가 존재합니다. 마지막으로 5~7 까지 3개를 더해주면 589+0+6+3 = 598개가 존재한다는 것을 알 수 있습니다.