[백준] 1748 - 수 이어쓰기1 in 파이썬

문제 출처

1748번: 수 이어 쓰기 1

 

문제

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

1234567891011121314151617181920212223...

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

 

입력

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

출력

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

---

문제 풀이

단순 구현으로 문제를 풀었더니 시간초과 오류가 발생했다.

따라서 규칙을 찾아서 최적화를 시켜줘야 했다.

 

 

N이 한 자릿수일 때, 이어쓰면 다음과 같은 결과를 가진다.

  N=1, 1

  N=2, 12

  ...

  N=8, 12345678

  N=9, 123456789

• 숫자(digit)은 1~9 중 하나의 값을 가지고,
• 한 자릿수의 수(number)를 계속 이어붙이기 때문에

=> 한 자릿수 중 최대값(9)을 이어쓴 자릿수는 9 = 9 * 1 이다.

 

 

N이 두 자릿수일때, 이어쓰면 다음과 같은 결과를 가진다.

  N=10, 12345678910

  N=11, 1234567891011

  N=19, 12345678910111213141516171819

  ...

  N=90, 12345678910111213141516171819...90

  N=99, 12345678910111213141516171819...90919293949596979899

 

즉, 한 자릿수의 길이를 제외하고, 두 자릿수만 따졌을 때 마찬가지로 규칙을 얻을 수 있다.

• 10개씩(e.g.10~19) 9번(10~19, 20~29,...,90~99)을 반복해서
• 두 자릿수의 수(number)를 계속 이어붙이기 때문에

=> 두 자릿수 중 최대값(99)을 이어쓴 자릿수는 90 = 9 * 10 * 2

 

 

 즉, 이러한 규칙을 이용해서 이어쓰기 자릿수를 구할 수 있다.

 

만약 N이 세 자릿수라면, 위의 규칙대로 (한 자릿수 최대값의 이어쓰기 자릿수) + (두 자릿수 이어쓰기 자릿수) 를 더한 뒤, 세 자릿수 범위에서 이어쓰기 될 개수를 구해서 더하면 될 것이다.

 

세 자릿수 범위에서 이어쓰기 될 개수는 길이 3의 수를 몇번 반복하느냐이므로,

"{N - (세 자릿수 최소값 = 100) + 1} * 3" 일 것이다.

 

 

이를 다시 정리해보자면

 

 

1)한 자릿수일 때, 한 자릿수 중 최대값(9)의 자릿수 = 9 * 10**0 * 1

2)두 자릿수일 때, 두 자릿수 중 최대값(99)의 자릿수 = 9 * 10**1 * 2

3)세 자릿수일 때, 세 자릿수 중 최대값(999)의 자릿수 = 9 * 10**2 * 3

 - digit은 1~9를 가질 수 있으므로 9 가지 경우의 수를 가지고

 - n의 자릿수일 경우, 1~9가 10**(n-1)번 반복되고

 - n의 자릿수만큼을 계속 이어 붙이기 때문에 (n의 자릿수)를 곱한

=> N의 자릿수가 가질 수 있는 최대값의 자릿수 = 9 * 10**{(N의 자릿수)-1} * (N의 자릿수)

 

즉, 원하는 숫자(N)의 이어쓰기 자릿수는

1. 숫자 N의 자릿수를 구한다

2. 한 자릿수부터 (N의 자릿수-1)자릿수까지 위에서 구한 공식으로 구한 뒤 모두 합한다

3. N의 자릿수가 가질 수 있는 최소값으로부터 N까지의 개수를 구한뒤, 개수에 N의 자릿수를 곱한다

   (예: N=125라면, 세자릿수 시작인 100에서 125까지의 개수를 구한다. -> 125-100+1 = 26 / 그 후 26*3)

4. 2번에서 구한 값과 3번에서 구한 개수를 모두 더한다

 

 

 

 

작성 코드

import sys
input = lambda: sys.stdin.readline()

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