12. 숫자의 총 개수(large)

문제

자연수 N이 입력되면 1부터 N까지의 자연수를 종이에 적을 때 각 숫자는 몇 개 쓰였을까요?
예를 들어 1부터 15까지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5으로 총 21개가 쓰였음을 알 수 있습니다.
자연수 N이 입력되면 1부터 N까지 각 숫자는 몇 개가 사용되었는지를 구하는 프로그램을 작성하세요.

입력설명

첫 번째 줄에는 자연수 N(3<=N<=100,000,000)이 주어진다.

출력설명

첫 번쨰 줄에 숫자의 총개수를 출력한다.

입력예제

15

출력예제

21

---

#include<stdio.h>
using namespace std;

int main(){
	freopen("input.txt", "rt", stdin);
	int n, i, j, digit=1, count=9, sum=0, result=0;
	scanf("%d", &n);
	
	while(n > sum + count){
		result = result + (digit * count);
		sum = sum + count;
		digit++;
		count = count * 10;
	}
	result = result + ((n - sum) * digit);
	
	printf("%d", result);
	
	return 0;
}

아 너무 어렵습니다 사실 이거보고 해설을 봐도 전 이해하기 어렵더군요.. 그치만 어렵다고 포기한다면 거기서 끝이니까 끝까지 해봅시다.

앞에 문제와 다른것은 입력되는값이 최대100,000,000입니다. 전처럼 푼다면 시간초과가 나는 것이죠.
그렇기에 우리는 최대한 효율을 살려서 알고리즘을 짜야합니다.

입력값이 256라면 1의자리 0~9 까지 9가지의 숫자가 쓰인것이고 + 10의 자리 10~99까지 90 * 2개의 숫자가 쓰인것입니다. 곱하기 2를 한 이유는 자릿수가 두개의 숫자들이기 때문입니다. 만약 주어지는 숫자가 999보다 크다면 100 ~ 999 * 3 을 하면 되는것이죠.
자 그럼 99까지의 숫자는 189개가 쓰인것이고 256에서 99를 빼고 * 3을 한것과 더하면 정답인 660이 나오는것입니다.