백준 - 수 이어 쓰기 2

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

1790번: 수 이어 쓰기 2

 

단순하게 탐색하면 시간초과가 난다.

파이썬이 1초에 약 1억번이라고 생각하면 된다고 알고 있었는데

아마 형변환하고 문자열 뒤에 붙이는 과정이 더 오래걸리는 것 같다.

앞으로 참고하면 좋을 듯 싶다.

 

그래서 최적화를 할까 뭐를 할까 고민했었는데 생각해보니깐 자릿수마다의 경우의 수는 정해져있다.

---

k에 해당하는 자연수의 자리수 특정하기

 

1의 자리 수

N이 1 -> 9로 증가하는 동안 N이 1 증가할 때마다 k가 가르키는 자리수도 바로바로 바뀐다

 

2의 자리 수

N이 10 -> 99로 증가하는 동안 N이 1 증가할 때마다 k가 가르키는 자리수도 2씩 넘어간다.

 

3도 마찬가지로 3씩 넘어가고 n의 자리수는 n씩 넘어간다.

 

이를 토대로 경우의 수를 계산해보자면,

각 자리의 끝 자리수는 1~9까지 9개의 경우의 수를 가지고

남은 모든 자리는 0~9까지의 10개의 경우의 수를 가진다.

 

수식화해보면 n의 자리 수가 문자열화하며 가질 수 있는 문자열의 길이는

9 + 9 * 2 * 10 + 9 * 3 * 10 ^ 2 + ... + 9 * n * 10 ^ (n-1)

 

수식에 따르면 1의 자리는 1~9, 10의 자리는 10 ~ 189, 100의 자리는 190 ~ 2889 ...

 

그럼 그 전까지의 자리수까지를 생각해 봤을 때 k가 어느 구간에 걸치냐를 따져본다면

구하고자 하는 자연수의 자리수를 특정할 수 있다.

---

이제 자연수를 추론할 수 있다.

 

현재 자리수의 범위에서 얼마만큼 더 가야하냐를 계산한다.

 

3자리 수라면 이전 자리수의 최대 k를 빼준 값으로 현재 얼마나 갔냐를 알 수 있다.

k가 190이라면 N은 3자리 수여야 하고 2자리의 범위인 189를 빼면 k는 1이 되고,

k는 3자리 수의 첫번째 수인 것을 특정할 수 있다.

 

이를 토대로 수식을 세워보면,

뺄셈한 k를 자리수로 나눈 몫을 구한다. 이유는 n의 자리의 수가 문자열화되면 n만큼 증가되기 때문이다.

 

자리수가 3이고, k가 190이라면 -> 뺄셈 후 1이 되기 때문에 3으로 나누면 0. 이는 3자리수의 0번째 수(100)를 뜻한다.

자리수가 3이고, k가 490이라면 -> 뺄셈 후 301이 되기 때문에 3으로 나누면 100. 이는 3자리수의 100번째 수(200)을 뜻한다.

 

몫이 자리수에서 몇번째 자리수인지를 나타낸다면 해당 자리수의 몇번째를 가르키는지 어떻게 나타낼까?

 

바로 나머지이다. 나머지는 몫을 통해서 특정지은 수의 좌측부터 몇번째 자리인지를 알려준다.

문자열화 저장하는 과정을 생각해보면 가장 높은 자리수가 먼저 들어온다.

 

10부터 저장한다고 생각했을 때,

123456789 다음에 10이 붙고 그다음 11이니까

1234567891011

- 10의 자리를 뜻하려면 k는 10과 11이어야 한다. 위의 과정을 따라왔다면 k는 1 or 2가 되고 나눈 몫은 0, 나머지는 0,1

- 11의 자리의 경우, k는 12, 13이어햐 한다. 마찬가지로 k는 3, 4가 되고 나눈 몫은 1, 나머지는 0,1

 

이렇듯 k가 특정하는 수의 높은 자리수부터 0부터 시작하기 때문에 123의 3을 뜻하려면 k 연산 나머지는 2이어야 한다.

 

정리하자면

연산하고 난 k의 나눈 몫 -> 현재 자리수에서 몫을 더하여 N을 구할 수 있다.

나머지 -> N에서 좌측부터 몇번째 자리인지 알려줌

---

 

연산 과정 정리

1. k가 몇의 자리의 수를 특정하는 지 구하고

2. k를 나누어 해당 자리 수의 몇번째 자리인지를 구하고

3. 나눈 나머지를 통해 해당 수의 좌측부터 몇번째인지를 구한다.

 

import sys
def input():
    return sys.stdin.readline().rstrip()

N, k = map(int,input().split())

digit = 1
while k > 0:
    tmp = 9 * digit
    for i in range(digit-1):
        tmp *= 10
    digit += 1
    k -= tmp

k += tmp - 1
digit -= 1

min_start = 10 ** (digit - 1)

share = k // digit

position = k % digit

goal_value = share + min_start

if goal_value > N:
    print(-1)
else:
    goal_value = str(goal_value)

    print(goal_value[position])