백준 1748 수 이어쓰기 1

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

1748번: 수 이어 쓰기 1

 

웬진모르겠지만 브루트포스에 섞여있어서,

1부터 n까지 모든 수의  len(str())을 더해서 풀었는데, 시간초과가 났다.

 

그래서방법을 갈구하다가,

자리의 규칙을 찾아냈다.

1+2+....+9=9     (10^0)*(9*1)

10+11.....+9=180 (10^1)*(9*2)

101+102+.....(999)=2700 (10^2)*(9*3)

 

예를 들어 n이 998이라면, 3자리이므로

먼져 999까지의 모든 숫자를 더해준다 9+180+2700=2889

 

여기서 999와 998의 차이를 구한다

999 (10^3-1) - 998=1

 

그후, 이 차이에 있는 숫자들은 모두 3자리이므로,

999까지 모두 생각한 결과에서, 차이에 있는 숫자들의 갯수 * 3을 빼준다.

 

2889-3*1=2886

 

문제는 엄청 쉬워보이고 코드도 간단한데 구현하기 꽤 까다로웠다.

##코드##

 

n=input()
ss=len(n) #몇자리수인지

answer=0
for i in range(ss):
    answer+= 9*(10**i)*(i+1)



answer -= ((i+1)* ((10**ss-1)-int(n) ))
print(answer)