[백준] 1748 수 이어쓰기 1 (파이썬)

문제 출처: 백준 온라인 저지

1748번: 수 이어 쓰기 1

 

문제 설명

🔎1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다. (1 ≤ N ≤ 100,000,000)
1234567891011121314151617181920212223...
이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.
(제한 시간: 0.15초, 파이썬은 0.5초)

해당 문제의 분류가 브루트포스로 되어있어서 설마 진짜 다 작성하고 len으로 구하는건가? 생각이 들어 작성해보니 역시나 시간초과가 떴다.

다른 방법을 생각했으나 해당 방법이 브루트포스인지는 명확하지 않다.

 

<정답 코드>

n = input()
cur = 1
answer = 0
while cur < len(n):
    answer += cur * (10**cur - 10**(cur-1))
    cur += 1

answer += cur * (int(n) - 10**(cur-1) + 1)
print(answer)

접근은 아래와 같다.

1. 한 자리 수 부터 시작해 입력 받은 수의 자릿수 -1까지 (자릿수 * 해당 자릿수에 존재하는 숫자 개수)만큼을 더한다.
2. 입력받은 수의 자릿수에 대해서는 (자릿수 * (입력받은 수 - 입력받은 수의 자릿 수의 첫번째 수))를 더한다.

한자리수일 때는 1~9, 9개가 존재하고, 두자리수일 때는 10~99, 90개, 세자리수는 100~999, 900개가 존재한다. 이와 같은 방법으로 계속 더 해나가는 것이다.

 

예를 들어 n = 1001이면 9+90+900+(4*2) = 1007이 되는 것이다.

내가 작성한 코드도 정답인 코드지만, 조금 더 직관적으로 작성하려면 while문 안에서 cur을 이용하기 보다 9로 시작해 9*10**(cur-1)로 진행해도 될 것 같다.

 

모든 숫자를 고려해야한다는 것은 사실이나, 기존 브루트포스 문제들과 같이 진짜 모든 경우를 방문하지 않는다는 점에서 브루트포스 문제인지 헷갈렸다.