수 이어 쓰기 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