[BOJ][Python]1748번 풀이

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

1748번: 수 이어 쓰기 1

n = int(input())
num = [100000000,10000000,1000000,100000,10000,1000,100,10,0]
ans = 0
for i in num:
    if n <10:
        ans += n
        break
    if n-i>=0:
        ans += (n-i+1)*len(str(i))
        n = int('9'*(len(str(i-1))))
print(ans)

아마 파이썬을 쓰시는 분은 다들 보자마자 문자열로 바꿔서 다 더한다음에 길이 출력하면 되겠네 하고 생각하셨을 것 같습니다. 저도 그랬구요. 다만 문제를 내신 분들도 그걸 고려해서인지 그렇게 풀면 시간초과가 나도록 되어있습니다. 그래서 접근법을 수정해야할 필요가 있었죠.

 

그래서 저는 1부터 10^8까지의 데이터가 내림차순으로 되어있는 리스트를 미리 만들었습니다(데이터의 최대값이 10^8이라서). 그리고 해당 리스트가 반복문을 통해서 i보다 n이 큰 경우 n-i+1개의 i와 같은 길이의 숫자가 있다는 뜻이니 i의 길이를 곱해서 더해줍니다. 그리고 n은 수정이 필요하니 i보다 1작은 숫자의 길이로 이뤄진 9의 배열을 정수로 바꿔서 저장해줍니다. 다음 i에 대해서도 구해줘야하기 때문에 n을 수정해줘야합니다. 이전 기준에 부합하는 경우는 이미 다 세어줬기 때문에 그 보다 작은 수에 대해서만 체크하기 위해 수정을 한다고 생각하시면 됩니다.