[백준/Python] #1748번 수 이어 쓰기 1

문제 

• 예를 들어 N이 5라면 1부터 5까지 이어붙인 수는 `12345` 이므로 5자릿수가 된다. 

 

입력

N(1 ≤ N ≤ 100,000,000)

5

 

출력

새로운 수의 자릿수

5

 

정답

import sys
input = sys.stdin.readline

N = int(input())

cnt = 0
tmp = len(str(N)) 

for i in range(1, tmp):
    cnt += 9 * 10 ** (i-1) * i
cnt += (N - 10 ** (tmp - 1) + 1) * tmp
    
print(cnt)

 

해결 아이디어

• 간단하게 for문을 사용해서 모든 숫자를 풀어낸 후 길이를 반환하는 방식을 먼저 떠올렸지만 N의 범위가 `1 ≤ N ≤ 100,000,000` 이므로 당연히 시간 초ㅈ과가 날 것이라고 생각했고, 다른 풀이를 적용했다. 
• 1~N까지 풀어낸 자릿수의 합을 구하기 위해서는 각 자릿수에 해당하는 수가 몇 개인지 알아내고 그 수의 길이를 구한 후 각 자릿수에서 구한 길이의 합을 구해주면 된다.
  1. 각 자릿수별 숫자의 개수를 구하려면?  
     • 자릿수=1 일 때, `1, 2, 3, 4, 5, 6, 7, 8, 9`로 총 9개(9*1)
     • 자릿수=2 일 때, `10, 11, 12,,,,20,,,30,,,,,,,,,90,,,,,99`로 총 90(9*10)
     • 자릿수=3일 때, `100,,,200,,,,,900,,999`로 총 900(9*100)
     • 위의 패턴을 따르자면 자릿수=N 이라면 총 9*(10의 N-1제곱) 이라는 식이 나오게 된다.
  2. 각 자릿수의 전체 길이를 구하려면?
     • 현재 자릿수의 숫자의 개수 * 현재 자릿수를 해주면 된다.
     • 예를 들면, 자릿수=2일 때 총 90개의 숫자를 가지고, 2자릿수 이므로 각 숫자마다 2의 길이를 가진다. 따라서 90*2=180의 길이를 가진다고 할 수 있다.
  3. 따라서 tmp(입력 받은 N의 길이)를 돌며 `9 * (10 ** i-1) * i`를 cnt에 더해주고, tmp 자리 숫자들은 따로 처리해줘야 하기 때문에 `(N - 10 ** (tmp - 1) + 1) * tmp`을 더한 값을 반환한다.