BOJ-백준 1748번 수 이어 쓰기 1 Python

BOJ-백준 1748번 수 이어 쓰기 1 Python 문제 풀이 입니다.

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

1748번: 수 이어 쓰기 1

 

✅ Python 정답 코드 입니다. 더보기 클릭!

n = int(input())
nn = n
count = 0
while nn>0:
  nn = nn//10
  count+=1
ans = 0
for c in range(1,count):
  ans += (10**(c)-10**(c-1)) * c
ans +=((n+1)-10**(count-1)) * (count)
print(ans)

 

📌 해설

1-9까지는 자릿수가 1씩 증가하고, 10-99가지는 자릿수가 2씩 증가하고 100 - 999까지 자릿수가 3씩 증가합니다.

N이 주어졌을때 1 - N까지 123456789101112 .. N-1N이라는 새로운 수의 길이가 얼마인지 구하는 문제입니다. 

 

🚩 주의

N이 최대 100,000,000 까지 주어질 수 있으므로 

1부터 N까지 모든 수를 문자열에 하나하나 더해서 문자열의 len()을 구하면 시간 초과되므로 

효율적으로 구하는 방법을 고민해야하는 문제입니다. 

 

n = int(input())
nn = n
count = 0
while nn>0:
  nn = nn//10
  count+=1

1. n을 입력받고 n의 자릿수를 구합니다.

2. nn을 통해 자릿수를 구해 count에 저장합니다. (len(str(n)) 으로 구하는 방법도 있습니다.)

 

ans = 0
for c in range(1,count):
  ans += (10**(c)-10**(c-1)) * c
ans +=((n+1)-10**(count-1)) * (count)
print(ans)

3. 1-9 까지 9개의 수가 있고 1씩 증가하며 자릿수를 증가시킵니다. 

10-99 까지 90개의 수가 있고 2씩 증가하며 자릿수를 증가시킵니다. 

100-999 까지 900개의 수가 있고 3씩 증가시키며 자릿수를 증가시킵니다. 

이를 식으로 바꾸면

으로 변경 할 수 있습니다.  ( C : 자릿수 )

4. N자리의 수를 마지막에 ans에 합산한 뒤 답을 출력합니다. 

 

만약 N이 120이라면 

for 문을 통해 

1-9까지 9개의 수를 1씩 증가시켜 ans에 합산,

10-99까지 90개의 수를 2씩 증가시켜 ans에 합산하고 for 문을 종료 한뒤

100-120까지 20개의 수를 3씩 증가시켜 ans에 합산하면 자릿수를 효율적으로 구할 수 있습니다.

 

 

 

::