코딩,안되면 될때까지

[백준 1748번-수 이어쓰기1]-파이썬 본문

백준/백준-파이썬

[백준 1748번-수 이어쓰기1]-파이썬

soo97 2022. 4. 23. 15:34
728x90
반응형

solved.ac 난이도 : Silver3

백준 1748번- 파이썬 풀이

<문제>

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

1748번: 수 이어 쓰기 1

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

www.acmicpc.net

<풀이>-구현,시뮬레이션

필자는 이 문제를 보고 처음엔 굉장히 단순하게 생각해 다음과 같은 코드를 작성했다.

n = int(input())
number = ""
for i in range(1,n+1):
    number+=str(i)

print(len(number))

n을 입력받은 다음 빈문자열 number를 선언해 1부터 n까지 number에 추가한후 number의 길이를 구하는 것이다. 하지만 역시나 이렇게 간단한 문제가 아니었고 시간초과로 인해 실패를 했다.

백준 문제 실패화면

따라서 어떻게 풀어야 하나 많이 고민하던 찰나 숫자의 자릿수에는 규칙이 있다는 것을 알게 되었다.

-한자리 숫자-

10**((숫자의 자릿수)-1)*(숫자의 자릿수) = 10**(1-1)*1 = 1*1 =1 (**는 제곱을 의미)

따라서 1~9까지 이어붙인 숫자의 자릿수는 9*10**(1-1)*1이 된다. (1~9 까지 9개의 숫자)

-두자리 숫자-

1) 10~19 : 10**((숫자의 자릿수)-1)*(숫자의 자릿수), 즉 10~19까지 이어 붙인 숫자의 자릿수는 20 이 된다.
(해당되는 범위의 숫자의 갯수)
2) 두자리 숫자의 경우 10~19,20~29,........90~99까지 9개의 범위가 존재하므로 두자리 숫자의 총 자릿수는 9*20 = 180이다.

-최종 공식-

숫자의 자릿수를 n이라 할때
자릿수가 n인 숫자들을 모두 이어붙여 만든 자릿수는 9*10**(n-1)*n이 된다.

여기서 9*10**(n-1)은 각 범위에 해당하는 숫자의 갯수를 의미한다. (2자리 숫자 90개(10~99), 3자리 숫자 900개(100~999))

따라서 문제의 예제 3을 보면 1~120까지 이어붙인 숫자의 자릿수를 구하라고 나와있다.

위의 공식에 맞춰, 1~9까지 이어붙인 숫자의 자릿수와, 10~99까지 이어붙인 자릿수, 100~120까지 이어붙인 자릿수를 구해서 더해주면 된다.

이때 100~120까지를 구할때는 세자리 숫자의 전범위를 구하는게 아니므로 100부터 120까지 숫자의 갯수를 구해서 해당 자릿수를 곱해준다.

728x90
반응형

<코드>-파이썬

n = input()
result = 0
for i in range(1,len(n)):
    result+=9*10**(i-1)*i
result +=(int(n)-10**(len(n)-1)+1)*len(n)
print(result)

-마치며-


이 문제의 핵심은 각 자릿수에 해당하는 숫자의 갯수를 구해 자릿수를 곱해주는것이다. 그러면 자연적으로 모든 숫자를 이어붙인 숫자의 자릿수가 나오게 되어있다. 필자는 처음에 이러한 생각을 못하고 무작정 단순히 풀려는 생각만해 실패를 했었다. 다 풀고 나니 생각보다 그렇게 어려운 아이디어는 아니었던거 같다.

728x90
반응형
Comments