brute force PS #boj 1748

문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다.

출력

첫째 줄에 새로운 수의 자릿수를 출력한다.

풀이1 (맞았으나 시간 초과)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define FASTIO   cin.tie(0);  cout.tie(0); ios_base::sync_with_stdio(0);

int digit(int c) {
    int x = 1;
    for (int i = 0; c / 10 > 0; i++) {
        c /= 10;
        x++;
    }
    return x;
}

int main() {
    FASTIO;
    int n; cin >> n;
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += digit(i);
    }
    cout << ans;
}

$O(nlog_{10}n)$ 이므로 시간 초과...

풀이2.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define FASTIO   cin.tie(0);  cout.tie(0); ios_base::sync_with_stdio(0);

int main() {
    FASTIO;
    int n;
    cin >> n;
    long long ans = 0;
    for (int start=1, len=1; start<=n; start*=10, len++) {
        int end = start * 10 - 1;
        if (end > n) {
            end = n;
        }
        ans += (long long)(end - start + 1) * len;
    }
    cout << ans << '\n';
    return 0;
}