[BOJ] 1748 - 수 이어 쓰기 1

문제

https://www.acmicpc.net/problem/1748

첫째줄에 N을 입력받아, 1부터 N까지의 수를 이어서 쓴 하나의 수의 자릿수를 구하여라.

 

예시)

n = 15

이어쓴 수 : 123456789101112131415
자릿수 : 21

 

풀이

틀린 풀이

N까지 이어서 쓴 수를 실제로 구한 뒤, 그 길이를 출력하는 방법을 썼다.

import sys

n = int(sys.stdin.readline())
print(len("".join([str(i) for i in range(1, n + 1)])))

무식한 방법이었는지, 메모리 초과로 틀린 풀이였다.

 

 

맞은 풀이

i번째 자리수가 등장하는 개수와 N과의 관계를 생각해보자.

자릿수	범위	개수
1번째 (1의 자릿수)	1 ~ N	N - 1 + 1
2번째 (10의 자릿수)	10 ~ N	N - 10 + 1
3번째 (100의 자릿수)	100 ~ N	N - 100 + 1
...
i번째(10^i의 자릿수)	10^i ~ N	N - 10^i + 1

 

위의 규칙을 이용해 i번째 자릿수를 누적한 값을 출력한다.

import sys

n = int(sys.stdin.readline())
c = 0
i = 1
while i <= n:
    c += n - i + 1
    i *= 10
print(c)