[BOJ] 1748번 - 수 이어 쓰기 1

---

문제설명

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

1748번: 수 이어 쓰기 1

사고과정

• 주어지는 데이터 범위 최댓값이 1억이기 때문에 일반 loop문으로 해결해서는 시간 초과가 분명히 발생한다.
• 따라서 고민을 많이 했는데.. 10의 자릿수(10의 제곱수) 기준으로 분할해서 1억까지의 누적 자릿수 합을 DP 테이블로 미리 만들어 놓고 N이 주어졌을 때, N의 자릿수보다 2보다 작은 인덱스값의 DP 테이블을 참조한다. 그리고 N 자릿수에서 1을 뺀 자릿수의 10의 제곱수와 N의 차이 + 1한 값에다가 N의 자릿수를 곱해주면 N과 동일한 자릿수의 10의 제곱수부터 N까지의 숫자를 붙여놓은 자릿수 값을 의미하게 된다.
• 참고로 DP 테이블에서 누적합을 구할 때 10억에 해당하는 값도 갱신되는데 이는 0으로 다시 초기화시키자. 그래야 N이 일의 자릿수가 들어왔을 때, DP[-1]을 참조하는데, 이 때 0을 참조할 수 있도록 했다.
• 포기하지 않고 고민을 끝까지 해서 규칙을 결국 파악해냈다..! 포기하지 않은 것에 의의를..!

풀이

import sys
input = sys.stdin.readline
# DP 테이블. 이 때 인덱스 값이 10 제곱수의 지수를 의미
dp = [0] * 10
dp[0] = 9
for i in range(1, 10):
    dp[i] = dp[i-1] + (pow(10, i+1) - pow(10, i)) * (i+1)
dp[-1] = 0

n = int(input())
length = len(str(n))
result = dp[length-2] + ((n - pow(10, length-1)) + 1) * length
print(result)