백준: 1748 수 이어 쓰기 1

문제

1748번: 수 이어 쓰기 1

 

문제 풀이

 브루트 포스로 풀면 시간 초과로 풀지 못한다. 그렇다면 어떻게 효율적으로 구할 수 있을까? 다음과 같은 경우를 생각해보면 쉽게 구할 수 있다.

 

• 자릿수는 몇 자릿수 인지를 의미한다. 예를 들어 1 ~ 9는 한 자릿수이다.
• 1 ~ 9 : 9개 * 자릿수
• 10 ~ 99 : 90개 * 자릿수
• 100 ~ 999 : 900개 * 자릿수

즉, 120의 경우 9 + 180 + ? 가 된다. 그럼 100과 120의 사이의 수들도 계산할 수 있다. (120 - 100 + 1) * 자릿수가 된다. 100과 120 사이의 값들 계산에서 +1을 해주는 것은 100도 포함되기 때문이다. 이와 같이 주어진 수의 자릿수에 따라 합산해가면서 구하게 되면 120의 경우 9 + 180 + 63으로 정답을 구할 수 있다.

코드

if __name__ == "__main__":
    n = input()
    length = len(n) - 1
    sum_length = 0
    for i in range(length):
        sum_length += 9 * (10 ** i) * (i + 1)
    sum_length += ((int(n) - (10 ** length)) + 1) * (length + 1)
    print(sum_length)