[백준] 5425. 자리합

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

문제요약

• a부터 b까지 각 숫자의 자리합 구하기(10^15)

접근법

• 일단 b까지의 자리합 - (a-1)까지의 자리합으로 접근함
• 숫자를 나눠서 접근해봄
• 0 ~ 99..99까지를 생각해보면
  • ${10^k}$가지의 경우의 수
  • 가장 앞자리를 1로 고정할때 나올 수 있는 경우의 수는 ${10^{(k-1)}}$
  • 숫자는 0부터 9까지 가능함
  • 고정할 수 있는 자리는 k개
  • ${(1 \times 10^{(k-1)} + 2 \times 10^{(k-1)} + ...) \times k = 45 \times k \times 10^{k - 1}}$
• 어떤 수 x와 가장 가까운 999...999까지 합을 구하고 나면 그 다음에 할 일은
• 100000 부터 x까지 구하는 일임
  • 자리수를 d라고 두면
  • 100..000 ~ 199...999, 200..000 ~ 299...999 로 나눠서 생각해볼 수 있음
  • 앞자리 1은 ${10^(d-1)} 번 나타남 + 뒤에는 999..999 까지의 합
  • 반복 예를 들어 x가 7232123..이면 1..., 2..., 6...까지 반복
• 이제 할 일은 x의 나머지를 구하는 일임
  • 일단 7은 7000... ~ 7232123... 까지 나타나기때문에 23123... + 1만큼 나타날 것임
• 그리고 나머지 232123....에 대해서 다시 자리수 합 계산을 수행함