[BOJ-1748]수 이어 쓰기 1

수 이어 쓰기 1 은 

입력으로 N~[1, 100,000,000] 의 수가 주어지고,

1부터 N까지 수를 순서대로 썼을 때 수가 만들어지는 자리수는 몇인지 구하는 문제임.

[입력]

N 

N~[1, 1억] 이 주어짐

[출력]

1부터 N까지 이어쓴 수의 자리수를 출력함.

규칙성이 있을 것이라고 판단해서 

1 부터 순서대로 작성해보았다. 

1 :  자리수 1 * 1 

2 :  자리수 1 * 2

..

9 :  자리수 1 * 9

10 : 자리수 1 * 9 + 자리수 2 * 1

11 : 자리수 1 * 9 + 자리수 2 * 2

..

19 : 자리수 1 * 9 + 자리수 2 * 10

..

29 : 자리수 1 * 9 + 자리수 2 * 20

..

99 : 자리수 1 * 9 + 자리수 2 * 90

100:자리수 1 * 9 + 자리수 2 * 90 + 자리수 3 * 1

109:자리수 1 * 9 + 자리수 2 * 90 + 자리수 3 * 10

...

999: 자리수 1 * 9 + 자리수 2 * 90 + 자리수 3 * 900

...

이런 규칙을 생각했다. 

각 자리수에 마다 최대 갯수는 9 * 10^자리수 이고, 이를 이용해서 문제를 풀 수 있다. 

예로 주어진 120은 

제일 작은 자리수(1) 의 갯수인 9 부터 시작한다. 

120 - 9 = 111

그 다음 자리수(2) 의 갯수인 90으로 빼어지는 지 확인한다. 

111 - 90 = 31

그 다음 자리수(3) 의 갯수인 900으로 빼어지는 지 확인한다.

31 - 900 < 0 이기 때문에 31은 현재 자리수의 갯수가 된다. 

이는 그대로 자리수(3) * 31 (개수) 를 더한다. 

이런 방법으로 접근하여 풀 수 있었음.

#include<cstdio>
#define llin1(a) scanf("%lld", &a)
typedef long long ll;
ll minus = 9; // 빼야할 값.
ll digit = 1; // 자리수.
ll n;
ll ans; // [1,n] 까지 자리수의 길이.
int main() {
    llin1(n);
    while (n > 0) {
        if (n - minus >= 0) ans += digit * minus;
        else ans += digit * n;
        
        n-=minus;
        digit++;
        minus *= 10;
    }
    printf("%lld", ans);
    return 0;
}