BOJ(수_이어쓰기1)(1748)

수 이어 쓰기 1

  • 1부터 N가지 수를 이어서 쓰면 새로운 하나의 수를 얻게 된다.

  • 123456789011121314151617192021…

  • 이 때, 새로운 수는 몇 자리 수일까?
  • (1<=N<=100,000,000)
  • 이 문제는 N이 1억이다.

  • N이 작다면,간단한 문제.
  • C++ 혹은 자바라면 직접 다 N을 세면서 문자열에, 정수를 문자열로 바꿔서, s의 길이만 바꿔주면 된다.

  • 새로운 수를 만드는데 공간 또한 매우 많이 든다.
  • 1억 / 2^30 (GB) -> 100MB

실제로 수를 만들지 않는 방법

  • 수의 자리수 별로 나누어서 문제를 해결할 수 있다.
  • N = 120
  • 1 ~ 9 길이 1 -> (9-1+1)*1
  • 10~99 길이 2 (99-10+1)*2
  • 100~120 길이 3 (120-100+1)*3

  • 수를 길이를 기준으로 건너 뛰었다.
  • N <= 1억 -> 9자리수.
n = int(input())
ans = 0
start = 1
length = 1
while start <= n:
    end = start*10-1
    if end > n:
        end = n
    ans += (end-start+1)*length
    start *= 10
    length += 1
print(ans)

참고자료 codeplus

0%