수 이어 쓰기 1

bookmark

문제

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

1234567891011121314151617181920212223...

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

입력

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

출력

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

나의풀이 1

n= int(input())
str_number=''
for i in range(1,n+1):
     str_number+=str(i)

print(len(str_number))

시간초과

나의풀이 2

n= int(input())
dp=[0]*(n+1)
dp[1]=1
for i in range(1,n+1):
    dp[i]=dp[i-1]+len(str(i))
print(dp[n])

메모리 초과

모범답안

n= int(input())

digit =len(str(n)) # 입력된 수의 자릿수 
count = 0

# 1의 자리부터 (digit-1) 까지의 숫자들의 개수 
# 1자리 9 개 
# 2자리 90 *2  개
# 3자리 900 * 3 개  

for i in range(digit-1):
    count += 9 *10 ** i *(i+1)
     

count +=(n-10**(digit-1) +1)*digit

print(count)

1~9 9개

10 ~ 99까지는 90 *2 개

100~999까지는 900 *3 개 순으로 증가한다.