[백준/파이썬] 1748번

📍백준 1748번 문제

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

코드

# 시간초과 코드

import sys
input = sys.stdin.readline

num = int(input())
cnt = 0
for i in range(1,num+1):
    cnt +=  len(str(i))

print(cnt)

# 답안 코드

import sys
input = sys.stdin.readline

n = int(input())
num = str(n)
cnt = 0

for i in range(1,len(num)+1):
    if i == len(num):
        temp1 = '1' + ('0') * (i-1)
        c = n - int(temp1)
        cnt += ((c+1)*i)
        # c+1 인 이유 : 10 100 1000 과 같은 수가 제외 되어있으므로 
    else:
        temp2 = '9' + ('0' * (i-1)) 
        cnt += (i * int(temp2)) 
print(cnt)

풀이

• 시간초과 코드:
  for 문의 범위 때문이 아닌가 싶었다. 결국 num만큼 for문을 돌려야하는 것이므로 숫자가 클 수록 더 많은 시간이 소요되기 때문이라고 예상한다.

• 답안 코드:
  숫자의 길이가 가장 중요한 포인트라고 생각했다. 그래서 for문의 범위를 숫자의 길이까지로 간주했다.
  그리고 숫자의 길이와 i 가 다르다면 그 범주 내에 있는 숫자들은 모두 포함되는 것이므로 (숫자의 길이가 i인 수의 개수) * i 를 해서 cnt에 더해주었다.
  숫자의 길이가 i 와 같다면 그 범주 내에서 숫자의 개수를 구해 i와 곱해 cnt에 더해주었다.