[C++] 숫자의 총 개수

📄문제

자연수 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 <iostream>
#include <string>

int main()
{
	int N;
	scanf_s("%d", &N);

	int answer = 0;
	int digit = 10;

	int digitCount = std::to_string(N).length();

	// 마지막 자리수 전 까지는 규칙대로 더하기
	for (int i = 1; i < digitCount; ++i)
		answer += 9 * std::pow(10, i - 1) * i;

	// 마지막 자리수에서 남은 개수를 구하기
	int left = N - (int)std::pow(10, digitCount - 1) + 1;
	answer += digitCount * left;

	printf("%d", answer);
}

• 각 자리수를 for문으로 계산하여 일일이 더할 수 있지만, 시간 복잡도와 자연수의 범위를 고려하여 규칙을 찾아 계산하는 방식으로 접근하였습니다.
• 예를들어 100일경우엔 1자리가 9개, 2자리가 90개이며, 나머지 세자리는 100 1개이기에 9 + 180 + 3으로 계산할 수 있습니다.