[Algo Rhythm🕺💃] BOJ 1748 - 수 이어쓰기 1

문제 분석

1️⃣. 나의 풀이

자연수 $i (1 \le i \le 8)$, $num \in [10^{i - 1}, 10^i)$를 만족하는 자연수 $num$, $num$에 따라 더해지는 글자 수, 그리고 $num$의 개수를 정리한 표는 아래와 같다.

 

입력으로 주어진 $n (1 \le n \le 10^8)$의 자릿수를 $\alpha$라고 하고 1부터 $n$까지 이어 쓸 때 만들어지는 새로운 수의 자릿수를 $f(n)$이라고 할 때, $f(n)$을 구하는 것이 이 문제의 핵심이다.

 

2️⃣. 다른 분의 풀이 (깔끔✨)

입력으로 주어진 $n (1 \le n \le 10^8)$ 이하인 모든 자연수들에 대하여 각 자리수 별로 나눠서 생각해보자.

1의 자리가 있는 수는 1부터 $n$까지 총 $(n - 1 + 1)$개이다.

10의 자리가 있는 수는 10부터 $n$까지 총 $(n - 10 + 1)$개이다.

이 과정을 $n$의 자릿수인 $\alpha$만큼 반복하면 $n$ 이하의 모든 자연수를 이었을 때 얻을 수 있는 새로운 수의 자릿수 $f(n)$을 알 수 있을 것이다.

 

문제 풀이

1️⃣. 나의 풀이

앞서 언급한 $f(n)$은 다음과 같다.

 

2️⃣. 다른 분의 풀이 (깔끔✨)

앞서 언급한 $f(n)$은 다음과 같다.

$\begin{matrix} f(n) &=& \sum n - 10^i + 1\ (i = 0, 1, 2, ..., \alpha - 1) \end{matrix}$

 

 

복잡도 분석

1️⃣. 나의 풀이

입력으로 주어진 $n (1 \le n \le 10^8)$의 자릿수를 $\alpha$라고 할 때, 시간 복잡도와 공간 복잡도는 다음과 같다.

⏰시간 복잡도 : $O(\alpha)$

$f(n)$을 구하기 위해 $O(\alpha)$가 소요됨.

🏠공간 복잡도 : $O(1)$

 

2️⃣. 다른 분의 풀이 (깔끔✨)

입력으로 주어진 $n (1 \le n \le 10^8)$의 자릿수를 $\alpha$라고 할 때, 시간 복잡도와 공간 복잡도는 다음과 같다.

⏰시간 복잡도 : $O(\alpha)$

$f(n)$을 구하기 위해 $O(\alpha)$가 소요됨.

🏠공간 복잡도 : $O(1)$

 

코드

1️⃣. 나의 풀이

 

2️⃣. 다른 분의 풀이 (깔끔✨)

 

문제 출처

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

1748번: 수 이어 쓰기 1