[백준 1748] 수 이어 쓰기1 (python)

https://www.acmicpc.net/status?user_id=edder773&problem_id=1748&from_mine=1 

채점 현황

수 이어 쓰기1 문제

1부터 N까지 수를 이어 쓸 때의 자리수를 출력해보자!

시간 초과를 해결하기 위한 탐색 수를 줄이는 방법을 생각하면 쉽게 풀 수 있는 문제

내가 푼 정답 코드

import sys
N = sys.stdin.readline().strip()
result = 0
if len(N) == 1: # 1의 자리일때는
    result = int(N) #그냥 바로 출력해!
else : # N이 1의 자리가 아니면
    result = 11 # 11부터 시작해보자 (N=10이면 11자리니까!)
    for i in range(2,10): # N이 최대 1억이니 9까지만 탐색해보자
        if len(N) == i: # N의 자리수를 찾았을 때!
            result += i*(int(N)-(10**(i-1))) #그 숫자의 자리수 *(그 숫자의 자리수-1에 해당하는 숫자 영역)을 해서 더해주자
            break
        else : # 자리수가 다르면
            result += i*(9*10**(i-1))+1 # 자리수에 해당하는 최대 갯수만큼 누적해서 더해놓자!
print(result)

이렇게 풀면 시간 초과

import sys
N = sys.stdin.readline().strip()
result = ''
for i in range(1,int(N)+1):
    result += str(i)
print(len(result))

📌 문제 접근 포인트

1. 문제를 처음 봤을 때 당연히 시간 제한에 뜨겠지만 위에 언급한 틀린 코드를 넣어봤다. (이렇게 쉬운 문제가 실버일리가 없어) → 이 과정에서 N의 범위가 최대 100,000,000이므로 1억번의 연산이 돌아간다. 당연히 굉장히 오랜 시간이 걸린다.
2. 그럼 N의 반복 연산 횟수를 줄여야 하니 N을 그대로 활용하는게 아닌 N의 자리수만 뽑아서 사용해보자 (len(str(N))을 활용하면 자리수만 바로 알 수 있다.
3. 어떤 식으로 반복되는지를 생각해보면 1의 자리면 1개씩 늘어나고, 2의 자리면 2개씩 늘어나고, 3의 자리면 3개씩 늘어나고 ··· 이런식으로 늘어난다.
4. 각 자리수에 해당하는 최대치는 1의 자리일 떄는 1*9, 2의 자리일 떄는 10~99까지니까 2*90, 3의 자리일때는 100~99까지니까 3*900 ··· 이런식으로 반복됨을 알 수 있다.
5. 그러면 N은 (N의 자리수-1)까지의 위 4번을 더하고,  N의 자리수에 해당하는 부분은 위 3번을 계산해서 더해주면 최종적으로 N을 이어붙인 수의 자리수를 알 수 있다.