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

www.acmicpc.net/problem/1748

1748번: 수 이어 쓰기 1

입력값의 범위가 최대 1억이므로 일반적인 방법으로는 시간초과를 피할 수 없습니다. 따라서 다음과 같은 아이디어가 필요합니다. 예를들어 입력값이 120이라고 치면

 

1 ~ 9 : 9개, 길이 : 1

10 ~ 99 : 90개, 길이 : 2

100 ~ 120 : 21개, 길이 : 3

9*1 + 90*2 + 21*3 = 9 + 180 + 63 = 252

 

자리수마다 숫자 개수를 구하고, 그 길이를 곱해준 후 모두 더해주면 됩니다.

 

#include <iostream>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
	long long res = 0;
    for(int start = 1, len = 1; start <= n; start *= 10, len++) {
    	int end = 10 * start - 1;
    	if(end > n) end = n;
    	res += (end - start + 1) * len;
	}
	cout<<res;
}