[코딩테스트] 숫자의 총 개수(large)

1. 문제

자연수 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까지 각 숫자는 몇 개가 사용되었는지를 구하는 프로그램을 작성하세요.

2. 입/출력 조건

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

- 출력 : 첫 번째 줄에 숫자의 총개수를 출력한다.(제한시간 1초)

 

3. 입/출력 예제

 - 입력 : 15

 - 출력 : 21

 

4. 풀이 소스코드

#include <iostream>
using namespace std;

int main() {
	int length;
	int cnt = 0, sum = 0, re=1;
	int max= 0 ;
	int nine = 9;

	cin >> length;

	if ((length < 3) || (length > 100000000)) return 0;

	// length = 256 1번째 max = 9 
	while (sum + 9 < length)
	{
		max = max + (re * nine); 
		sum = sum + nine; //9개
		re++;
		d = d * 10; // 다음 자리 숫자 계수

	}

	max = max + ((length - sum) * re); //통과가 안된거
	cout << max;

 

❕ 피드백

자릿수를 하나하나 10으로 나눌 때 마다 카운트하는 접근 방식은 1초를 넘어버린다. (T_T)

 

결국 강의를 봤다. 

각 자리수의 개수를 구하는 접근 방법 : N의 자리수 만큼 곱해진게 사용된 숫자의 총 개수

1자리 수라면 그 숫자는 9개가 사용되었을 거고

2자리 수라면 그 숫자의 *2가 사용된 숫자의 총 개수(10-99까지 총 180개의 숫자가 사용됨)

3자리 수라면 그 숫자의 *3이 사용된 숫자의 총 개수(100-999까지 총 2700개의 숫자가 사용됨)