BOJ 1748. 수 이어 쓰기 1

• 문제링크 : https://www.acmicpc.net/problem/1748

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.
1234567891011121314151617181920212223...
이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

1. 문제 해석

• N이 너무 크기 때문에, 실제로 수를 만드는 것은 너무 시간이 오래 걸린다.
• 총 N개의 수를 하나의 문자열로 만들어야 한다.
• O(N) × 10 -> 최대 1억 번
• 여기서 10은 수의 최대 자릿수를 의미한다.

1 2 3 4 5 6 7 8 9 / 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ... 99 / 100 101 ... 999 ...
일단 1부터 N까지의 수를 나열해보면, 한 자리 수는 9개이고, 두 자리 수는 99-10+1 개이고, 세 자리 수는 999-100+1 개 이다.

즉, 수의 자리수별로 나누어서 문제를 해결할 수 있다.
• N = 120 이면
• 1 - 9 → (9-1+1) × 1
• 10 - 99 → (99-10+1) × 2
• 100 - 120 → (120-100+1) × 3

2. 문제 풀이

#include <iostream>
using namespace std;
int main() {
    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) { // N=120인 경우 999>120 이므로, 예외처리
            end = n;
        }
        ans += (long long)(end - start + 1) * len;
    }
    cout << ans << '\n';
    return 0;
}