[백준] 수 이어 쓰기 1

문제

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

1748번: 수 이어 쓰기 1

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

1234567891011121314151617181920212223...

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

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

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

예제 입력 1 
5

예제 출력 1 
5

---

풀이

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

n = int(input())
ans = 0
for i in range(len(str(n))-1):
    ans += 9*(10**i) * (i+1)
ans += (int(n) - 10**(len(str(n))-1) + 1) * len(str(n))
print(ans)

 

첫 풀이

import sys
input = sys.stdin.readline

n = int(input())
ans = str(1)
for i in range(2, n+1):
    ans += str(i)
print(len(ans))

---

설명

처음에 풀었던 것처럼 푸니 시간초과가 발생했다. 분명 무슨 공식이 있을것 같았는데 결국 다른 사람 풀이를 봤다. 근데 다른사람의 풀이를 봐도 처음엔 이해가 잘 되지 않았었다..ㅎ

 

풀이 과정)

1. n 이 최대 100,000,000 이므로 1억 번의 연산이 발생한다. => 굉장히 오랜 시간이 걸린다..

2. n의 반복 연산 횟수를 줄여야 하니 n 을 그대로 활용하는것이 아닌 n 의 자리수만 뽑아서 사용해보자! 

 len(str(n)) 을 활용하면 자리수만 바로 알 수 있다.

3. 아래와 같이 반복됨을 알 수 있다.

1의 자리인 1~9: 1개씩 늘어남 => 1*9

2의 자리인 10 ~ 99: 2개씩 늘어남 => 2*90

3의 자리인 100 ~ 999: 3개씩 늘어남 => 3*900 

4. n 은 (n의 자리수 - 1) 까지의 위 3번을 더하고, n의 자리수에 해당하는 부분은 위 2번을 계산해 더해주면 최종적으로 n을 이어붙인 수의 자리수를 알 수 있다. 

 

최종 규칙!

자리수가 n인 숫자들을 모두 이어 붙여 만든 자리수는 9 * 10 * (n-1) *n 이 된다!

여기서 9*10**(n-1) 은 각 범위에 해당하는 숫자의 개수를 의미한다. (2자리 숫자 90개(10~99), 3자리 숫자 900개(100~999))