[백준] 1748번 수 이어 쓰기 1 - Python / 알고리즘 기초 2/2 - 브루트 포스

---

---

---

💡 문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다.

출력

첫째 줄에 새로운 수의 자릿수를 출력한다.

---

💭 접근

우선 이 문제는 단순히 아래 코드와 같이 n번을 반복하면 최대 입력의 범위가 100,000,000 이기 때문에 시간초과가 발생한다.

for i in range(1, n + 1):
	ans += len(str(i))

따라서 다른 방식으로 접근해야 하는데, 각 자리수마다 숫자의 개수를 구해주면 된다.

1자리 (9개) 1 ~ 9
2자리 (90개) 10 ~ 99
3자리 (900개) 100 ~ 999

이러한 점을 이용해 (각 자리의 숫자의 개수 x 자리수)를 해주면 최대 9번의 반복 만에 답을 구할 수 있다.

---

📒 코드

n = int(input())
num_len = len(str(n))

ans = 0
base = 0
for i in range(1, num_len):
    base = base * 10 + 9
    ans += (base - 10**(i - 1) + 1) * i

ans += (n - 10**(num_len - 1) + 1) * num_len
print(ans)

---

💭 후기

각 자리의 숫자를 구하는 법을 떠올렸다면 쉽게 풀릴 문제.

---

🔗 문제 출처

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

---