백준[ 1790 | Python ] 수 이어 쓰기 2

문제

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

풀이

입력이 N기준 최대 1억임에도 불구하고 시간 제한은 7초이다.
1부터 1억까지 이어쓰기에 시간이 부족하기에 다른 방법을 생각했다.

먼저 k가 1~9의 범위 안에 있다면 자리수는 한자리이다. k가 10~99의 범위 안에 있다면 자리수는 두자리이다.
위와 같이 k에서 자리수에 자리수를 늘려가며 맞게끔 9x1, 90x2, 900x3, … 을 빼준다.
이유는 1~9 는 각 숫자마다 1자리씩이지만 10~99부터는 각 숫자마다 2자리 이상이기 때문이다.

그렇게 k에서 자리수에 맞게 빼주다보면 더 이상 뺄 수 없는 값이 나온다.
이 때 k가 어느 수에 속하는지 알기 위해 k를 지금까지 세어온 자리수 만큼으로 나눈 뒤
그 값을 더해준다. (k가 300인 경우 그 자리수인 3으로 나눠주면 원하는 값이 100이 나온다.) k 로 원하는 수를 찾았으면 n과 대소비교를 한 뒤 값을 내면 된다.

n, k = map(int, input().split())
ans = 0
digit = 1
nine = 9


while k > digit*nine:
    k = k-(digit * nine)
    ans = ans + nine
    digit+=1
    nine = nine*10

ans = (ans+1) + (k-1) // digit

if ans > n:
    print(-1)
else:
    print(str(ans)[(k-1)%digit])

생각 & 정리

10~99, 100~999 … 사이의 값이 90개가 아니라 89개라고 생각해서 한참 해멨다.