1748번: 수 이어 쓰기 1
첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다.
www.acmicpc.net
1748. 수 이어쓰기 1
접근한 방법
단순한 유형의 브루트포스 문제입니다. 수의 범위를 보면 최대 1억번입니다. 적당한 시간이 주어진다면 일반적으로 O(n)복잡도로 해결 가능한 범위이지만 이 문제의 경우 제한 시간이 매우 타이트하므로 n번 이내로 해결해야 합니다.
수학적으로 접근합니다. 규칙을 자세히 찾아보면 굳이 일일이 자릿수를 더해줄 필요가 없습니다.
어떤 수의 각 자릿수마다 나올 수 있는 최대 길이는 정해져있습니다.
예를 들면 1개 자리는 1 ~ 9이므로 9번 * 1, 2개 자리는 10~99이므로 90번 * 2, 3개 자리는 100~999이므로 900번 * 3 ...
그러면 범위가 [9, 180, 2700 ...] 와 같이 나오게 되고 이것을 이전 값과 누적해주면 아래와 같은 범위를 만들 수 있습니다.
[9, 189, 2889, 38889, 488889, 5888889, 68888889, 788888889]
이 범위를 만들어놓은 이유는 다음과 같습니다.
예를 들어 1255라는 수가 주어졌을 때, 999, 즉 3개자리까지는 이미 위와 같이 길이를 구해놨습니다. 그러므로 먼저 2889를 더해줍니다.
이후 4개 자리를 더해주기 위해 남은 횟수는 1255 - 999입니다. 이 값에 4를 곱한 값을 마저 더해주면 2889 + 256 * 4 = 3913이라는 결과를 바로 만들어낼 수 있습니다.
이렇게 접근하면 어떤 값이 들어와도 모두 O(1)의 복잡도로 해결할 수 있습니다.
Python 풀이
import sys
input = sys.stdin.readline
n = int(input())
d = [0, 9, 189, 2889, 38889, 488889, 5888889, 68888889, 788888889]
nlen = len(str(n))
print(d[nlen - 1] + nlen * ((n - 10 ** (nlen - 1)) + 1))