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

수 이어 쓰기 문제는 N이 주어지면 1부터 N까지의 숫자를 그대로 이어썼을 때 몇자리 숫자가 될 것인지를 물어봅니다.  무한대의 수를 소수로 만들면, 이 수는 초월수가 된다는 것이 증명되었는데, 비슷한 개념이지만, 여기는 유한개의 수를 붙여 쓰는 것이고, 자릿수만 계산하면 되는 문제라 어려운 수학이라고 보기는 힘듭니다.

 

 

한자리 숫자는 9개가 있고, 두자리 숫자는 90개가 있고, 세자리 숫자는 900개가 있습니다.  k자리숫자는  \( 9 \times 10^{k-1} \)개가 있게 됩니다.  이를 이용하면 이 문제를 쉽게 풀 수 있습니다.

 

예를 들어서 372까지의 숫자를 쓴다고 해보죠.

1) 9보다 큰 수이므로 9자리가 나옵니다.

2) 9를 빼면, 363이 되고 이 수는 90보다 크므로, 189가 됩니다.

3) 90을 빼면 273이 되고, 이수는 900보다 작으므로 1018이 됩니다.

이렇게 하면 답이 1018이 나오게 됩니다.

 

예제로 나온 120이라면

1) 9보다 큰 수 이므로 일단 9가 됩니다.

2) 9를 빼면 111이 되고 이 수는 90보다 큰 수이므로 189가 됩니다.

3) 90을 빼면 21이 되고 이 수는 900보다 작으므로 252가 됩니다.

그래서 답은 252가 됩니다. 

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//------------------------------------------------
//    baekjoon #1748
//        - by Aubrey Choi
//        - created at 2019-06-28
//------------------------------------------------
#include <stdio.h>

int main()
{
    int n, s = 0;
    scanf("%d", &n);
    for(int t = 9, k = 1; n; t *= 10, k++)
    {
        int r = (n > t) ? t : n;
        s += r * k;
        n -= r;
    }
    printf("%d\n", s);
    return 0;
}