문제:
1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.
1234567891011121314151617181920212223...
이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 N(1<=N<=100,000,000)이 주어진다.
출력:
첫째 줄에 새로운 수의 자릿수를 출력한다.
풀이방법:
처음에는 브루트 포스로 알고리즘 분류가 되어 있어서 그냥 N까지의 수를 다 붙인 다음에 길이를 구하는 방식으로 했는데 시간초과가 발생했다.
|
1
2
3
4
5
6
|
#시간초과
n=int(input())
answer=''
for i in range(1,n+1):
answer+=str(i)
print(len(answer))
|
cs |
그래서 처음 받은 N을 기준으로 자릿수를 줄여나가면서 더하는 방식으로 바꾸어서 해결을 했다.
ex) 3자리수의 갯수*3 + 2자리수의 갯수*2 ....
|
1
2
3
4
5
6
7
8
9
|
n=input()
answer=0
length=len(n)
while length:
answer+=(int(n)-10**(length-1)+1)*length
n=10**(length-1)-1
length-=1
print(answer)
|
cs |
문제링크:
https://www.acmicpc.net/problem/1748
1748번: 수 이어 쓰기 1
첫째 줄에 N(1≤N≤100,000,000)이 주어진다.
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]2644. 촌수계산 (0) | 2020.03.24 |
|---|---|
| [BOJ]2352. 반도체 설계 (0) | 2020.03.19 |
| [BOJ]1267. 핸드폰 요금 (0) | 2020.03.12 |
| [BOJ]2579. 계단 오르기 (0) | 2020.03.10 |
| [BOJ]13458. 시험 감독 (0) | 2020.03.05 |