[Python] 백준 1748 수이어쓰기

1748 수이어쓰기

 

문제

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

1234567891011121314151617181920212223...

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

입력

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

출력

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

 

문제풀이

본 문제는 수학적으로 해결하는 문제이다.

각 숫자의 자릿수를 계산해서 기록하는 문제이며, 시간이 매우 짧기 때문에

자릿수를 계산할 수 있는 방법을 기록해야 한다.

 

start 변수를 통해 현재의 자릿수 계산을 시작한다.

end 변수로 현재 자릿수 범위의 끝 값을 계산한다.

end=min(start×10−1,N)

 

예를 들어서, 13이 N이라면,

처음에는 9와 13을 비교한다.

 

물론 9가 더 작기 때문에, 현재 자릿수의 마지막 값은 9가 될 것이다.

그렇게 해당 자릿수에서 셀 수 있는 숫자의 개수를 기록할 수 있게 되며,

기록된 값을 중심으로 현재 자릿수에 대한 값을 누적한다.

 

이어서 다음 10의 자리를 확인할 때는,

19와 13을 확인하고, 더 작은 값은 13이기 때문에,

마지막 끝 값은 13이 될 것이다.

 

그렇게 해당 범위의 숫자의 개수를 확인하고,

자릿수 길이만큼을 곱해서 더해준다.

 

이렇게 모든 자릿수를 탐색하면 끝이 난다.

 

정답코드

def count_digits(N):
    digits = 0  # 전체 자릿수를 저장하는 변수
    length = 1  # 현재 자릿수를 나타냄 (한 자리 수부터 시작)
    start = 1   # 각 자릿수의 시작 값 (1, 10, 100, ...)

    while start <= N:
        # 현재 자릿수 범위의 끝 값 계산
        end = min(start * 10 - 1, N)  
        
        # 해당 범위의 숫자 개수 계산
        count = end - start + 1
        
        # 전체 자릿수 계산: 자릿수 길이 * 해당 범위의 숫자 개수
        digits += count * length
        
        # 다음 자릿수로 넘어감
        length += 1
        start *= 10

    return digits

# 입력 값 받기
N = int(input())
print(count_digits(N))