[백준 알고리즘][파이썬/Python] 1748번: 수 이어 쓰기 1

문제

시간 제한 : 1초, 메모리 제한 : 128 MB

 

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

1234567891011121314151617181920212223...

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

 

입력

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

 

출력

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

 

입출력 예

 

제출 코드

n = int(input())
lst = [9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999]
max = 0
len = 0
for idx, val in enumerate(lst):
    if n < val:
        max += 1
        break
    else:
        max = idx + 1
        len += max*int('9'+'0'*idx)

if max == 1:
    print(n)
else:
    len = len + (n-pow(10, max-1)) * max + max
    print(len)

문제의 핵심

# 1

내가 푼 방법이 특별한 것인지 일반적인 것인지 전혀 감을 잡지 못하겠다. (사실 다른 블로그들을 찾아보면 될 텐데 너무 귀찮다...) 아무튼 중요한 것은 자신만의 공식이든 점화식이든 그 무언가를 만들어내야 한다는 것이다. 역시 문제 분류가 '수학'인 만큼 살짝... 까탈스럽다.

 

라인 별 풀이

(1) line 2

입력값 n이 몇의 자리 수인지 확인하기 위해 임의로 만든 리스트이다.

 

(2) line 3, 4

입력받은 n이 몇의 자리 수인지 확인하기 위한 변수 max와

결과값으로 출력할 새롭게 만들어진 수의 길이를 담기 위한 변수 len을 선언한다.

 

(3) line 5 ~ 11

입력받은 n의 자릿수를 하나씩 올려가며 확인하며 len을 차근차근 늘려가는 과정이다. 문제에서 주어진 예제 입력 '120'을 가지고 설명할 것인데, 순차적으로 코드의 로직을 따라가 보자.

 

1. lst를 순회할 때 처음 val 값은 9이다. 120(=n)은 val보다 크므로 else 구문에 적용된다. n은 9보다 크기 때문에 적어도 한 자리 이상의 수이므로 idx(=0)+1을 해줘서 max에 1을 할당한다. 그와 동시에 0으로 초기화되어있는 변수 len에 새롭게 만들어진 수의 길이를 더해줘야 하는데, 코드에 따라 len에 9가 더해진다. 왜냐하면 '123456789'가 이어 붙을 것이기 때문에 9를 더해준다.
2. lst 순회를 한 번 더 하였을 때 val 값은 99이다. 120은 val보다 크므로 else 구문에 적용된다. n은 99보다 크기 때문에 적어도 두 자리 이상의 수이므로 idx(=1) + 1을 해줘서 max에 2를 할당한다. 그와 동시에 9라는 값을 담고 있는 변수 len에 새롭게 만들어진 수의 길이를 더해줘야 하는데, 코드에 따라 len에 180이 더해진다. 왜냐하면 '1011121314...99'가 이어 붙을 것인데, 이어 붙는 각각의 수는 2의 길이를 가지고 있고 그 수가 총 90개이기 때문이다. 
3. lst 순회를 한 번 더 하였을 때 val 값은 999이다. 120은 val보다 작으므로 if 구문에 적용된다. n은 100 이상 999 미만의 수이므로 세 자리 수라는 것이 밝혀졌고, 그에 따라 기존의 max에 담긴 값에 1을 더해주고 반복문을 종료한다.

 

(4) line 13, 14

만약 (3)에서 max가 1인 상태로 종료되었다면 (즉, 한 자릿수였다면) 어차피 붙는 수는 '123...n'이므로 그대로 print(n)을 해준다.

 

(5) line 15 ~ 17

n이 한 자리 수가 아니었다면 (3)에서 len에 반영하지 못한 수들이 남아있다. 예제 입력으로 주어진 120을 생각해봤을 때, (3)에서는 '123...979899'까지 만을 고려하고 반복문이 종료되었기 때문에 더 이어 붙여야 할 100, 101, 102, ..., 120을 len에 추가적으로 반영해줘야 한다. 그 과정이 line 16이다.

 

 

실패 기록

n = int(input())
lst = [str(i) for i in range(1, n+1)]
s = ('').join(lst)
print(len(s))

귀차니즘으로 인해 그냥 진짜 수를 붙여버리고 1분 만에 첫 제출을 했었는데, 최악의 경우 N이 1억까지 갈 수 있으므로 당연히 메모리가 터져버렸다. 까비!

 

 

 

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