[C++][백준] - 수 이어 쓰기 1 (1748번)

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

1748번: 수 이어 쓰기 1

🔔 문제 : 

1<= N <= 100,000,000 범위에서

 

1 ~ N 까지 이어붙힌

1234567891011121314151617181920212223...의 새로운 수의 자릿수를 구하는 문제입니다.

---

🔔 Kick Point :

F(x)가 숫자 x의 자리수의 갯수라 정해보면 

 

만약 N = 1001 인 경우,

F(1) + F(2) .... + F(9) +

F(10) + F(11) .... + F(99) +

F(100) + F(101) .... + F(999) +

F(1000) + F(1001)

= (9 * 1) + (90 * 2) + (900 * 3) + (2 * 4) 인 셈입니다.

 

 

1 <= x <= 9  :  F(x) = 1

10 <= x <= 99  :  F(x) = 2

100 <= x <= 999  :  F(x) = 3

1000 <= x <= 9999  :  F(x) = 4

..........

10,000,000 <= x <= 99,999,999 : F(x) = 8

100,000,000 : F(x) = 9

 

F(X)값은 이런식으로 흘러 갑니다.

 

미리 N의 자리수 F(N)보다 적은 값들의 합을 구해두고

F(N)의 자리수만 따로 구하면 시간 제한조건에 맞게 잘 구할 수 있습니다.

 

---

🔔 Code :

 

 

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	long long int n; // input
	long long int output = 0; // output
	
	int k =0; // n의 자릿수
	int bucket[10] = { 0, }; // 0은 제외한 1부터 9번째까지의 자릿수 합 ex) n[1] = 9*1 ,n[2] = 90*2
	
	for (int i = 1; i < 10; i++) {
		bucket[i] = 9 * i * (long long int)pow(10, i - 1);
	}
	
	cin >> n; // 1<= n <= 100,000,000

	for (int i = n; i != 0; i /= 10) {
		k++;
	}

	for (int i = 1; i < k; i++) {
		output += bucket[i];
	}

	output += (n - pow(10, k - 1) + 1) * k;
	
	cout << output;
}

bucket[n] = 자릿수 n들의 합

 

---