[백준_1748] 수 이어 쓰기1 python

https://www.acmicpc.net/problem/1748

1748번: 수 이어 쓰기 1

문제

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

1234567891011121314151617181920212223...

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

입력

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

출력

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

 

문제 해결

1부터 N까지의 수를 이었을때의 자릿수를 출력하는 문제이다.

N의범위가 1억까지이기 때문에 반복문을 통해 문제를 해결하려하면 O(N)시간복잡도로 시간초과든 메모리초과든 날것같다는 생각을 가져야한다.  문제에서 추가로 주어진 조건이 없으니 출력조건을 집중해 봐야한다.

 

우리는 '자릿수'만 출력을 하면 되기때문에 자릿수개념으로 접근해본다. 

1자리수는 0~9까지의수 ( 문제에서는 1부터 주어진다)

2자리수는 10~99까지의수

3자리수는 100~999까지의수

.

.

8자리수는 10,000,000~99999999

9자리수는 100,000,000~(1억이하가 문제의 조건이다.)

이와같이 생각해보면 자리수 n과 미지수 x에 대해서 아래와같은 규칙을 찾을 수 있다.

(n=0, x는 한자리수),(n=1, x는 두자리수),(n=2, x는 세자리수)....

10^n  <= x <= 10^(n+1) - 1

 x가 151인경우로 예를 들면, 151은 10**2이상 999이하의 숫자이다. n은 2와 1 그리고 0 세번에 걸쳐 계산을 해야한다.

151은 

1부터9 -> 9개 >>> 9*1

10부터99 -> 90개 >>> 90*2

100부터 151 -> 52개>>>> 52*3

위와같이 계산을 하면 345라는 숫자를 얻을 수 있다.

1억은 9자리숫자이기에 9번의 반복문을 통해큰숫자부터 고려해주어 아래와같이 코드를 작성하였다. 

 수학,구현문제이기 때문에 여러가지 풀이가 많은 것 같다.

n = int(input())
ans=[]
def f(x):
    for i in range(9,-1,-1):
        if 10**i <= x <= 10**(i+1)-1:
            cha = (x-(10**i-1))
            res = cha*(i+1)#윗자리수
            ans.append(res)
            f(10**i-1)
f(n)
print(sum(ans))