[백준(BOJ)] 1748번 : 수 이어 쓰기 1 - PYTHON[파이썬]

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

1748번: 수 이어 쓰기 1

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 수학
• 구현

 

---

 

⊙ 문제 접근 과정

 

N = int(input())

input_ = ""

for i in range(1,N+1):
    input_ += str(i)

print(len(input_))

처음에는 위와 같이 코드를 짰다. 하지만 시간 초과.

dp처럼 공식을 세워서 문제를 풀어야지 주어진 시간제한 안에 문제를 풀 수 있었다.

 

가만 생각해보니 패턴이 존재했다.

 

1부터 9까지의 값의 합이 아닌 자릿수의 합은 9이다.

마찬가지로 10부터 99까지 자릿수의 합은 90

100부터 999까지의 자릿수의 합은 900

 

따라서 공식을 세울 수 있다. 아래 코드에서 확인해보자

---

 

⊙ 문제 풀이

 

from sys import stdin

N = int(stdin.readline())

len_N = len(str(N))

count = 0

for i in range(len_N -1):
    count += 9 * 10 ** i * (i+1)

print(count + (N - 10**(len_N-1) + 1) * len_N)

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

알고리즘을 해결할 때, 기본적인 수학상식이 있으면 도움이 많이 된다.

 

좋아요는 로그인하지 않아도 누를 수 있습니다!