0부터 n까지의 자리수의 합을 구하는 함수를 D(x)라고 할때, 아래의 값들을 미리 별도의 방법으로 계산하여 저장해두었다.
sumexp = [0, 45, 900, 13500, 180000, 2250000, 27000000, 315000000, 3600000000, 40500000000]맨 앞의 0을 제외하고는, 각각 D(10^n - 1) 의 값을 담고 있다.
함수 D(x)에서는 주어진 수를 1의 자리, 10의 자리, ... 단위로 계속해서 값을 빼가면서 0이 될때까지 값을 구하게 된다. 이때 제일 중요한건 (1-9 이내의 정수인 k에 대해) k * 10^n부터 (k+1) * 10^n - 1까지의 값이 k * (10^n) + D(10^n-1) 이라는 것이다.
예를 들어, k가 6이고, n이 3이라고 가정하면 3000부터 3999 이내의 범위가 나오는데 이때 이 범위의 합이 3 * 1000 + D(999) = 16500 이 된다. 이러한 과정을 대략 아래와 같은 방식으로 반복한다. 단 1의 자리의 경우는 n이 많아봐야 10이기 때문에 소스코드의 sumd(x)함수를 통해 직접 연산한다.
x가 1234일때의 예시.
x = 1234
x: 1234 -> 1230, n: 1, result에 1230~1234의 합 추가
x: 1230 -> 1220, n: 2, result에 1220~1229의 합 추가
x: 1220 -> 1210, n: 2, result에 1210~1219의 합 추가
x: 1210 -> 1200, n: 2, result에 1200~1209의 합 추가
x: 1200 -> 1100, n: 3, result에 1100~1199의 합 추가
x: 1100 -> 1000, n: 3, result에 1000~1099의 합 추가
x: 1000 -> 0, n: 4, result에 0~ 999의 합 추가
대략 이런 반복 과정을 거쳐서 D() 함수의 값이 나오게 된다.
이후 출력값은 D(upper) - D(lower - 1) 로 구하여 출력하면 된다. 끝!
더 깔끔하게 푸는 방법이 있는 것 같으나 머리가 안굴러가서 거기까진 못하겠다.