[구현/수학] 백준 1748 수 이어쓰기 1 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1748번: 수 이어 쓰기 1

 

 

 

2. 문제 풀이

123456789 10111213141516 ... 100101102

 1부터 N까지의 수를 이어서 쓸 때, 그 수의 길이를 구하는 문제입니다.

 

2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학

[Algorithm] 단골 1번 문제, 구현 / 수학

 시간제한이 굉장히 빠듯한 편입니다. 단순히 숫자가 올라갈 때마다 자릿수를 계산하면 '시간초과'가 납니다. 규칙을 찾아야 합니다.

 

1자릿수: 1~9 => 9개
2자릿수: 10~99 => 90개
3자릿수: 100~999 => 900개
...

 자릿수를 digit이라고 할 때, 해당 자릿수의 숫자는 9 * 10^(digit-1) 개입니다.

 

 

3. 코드

N = input()
digit = len(N) #자릿수

res = 0 # 결과값
# 이전 자릿수까지의 합
for i in range(digit):
    # 해당 자릿수의 숫자 개수 * 자릿수
    res += (9 * (10**(i-1))) * (i)

# 현재 자릿수의 합
# N의 자릿수에서 N까지의 숫자 개수 * N의 자릿수
res += (int(N) - 10**(digit-1) + 1) * digit
print(int(res))

 이전 자릿수까지의 숫자들의 합과, 현재 자릿수에서 N까지의 합을 구합니다.