[PS] BOJ1790 수 이어 쓰기2 ( 이분탐색 ) With 파이썬

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

1790번: 수 이어 쓰기 2

 

 

◎ 문제풀이

 

개인적으로 어려운 문제라 아래 포스팅을 참고하여 풀었다.

 

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

 

 

수를 1부터 n까지 이어붙였을 때 k번째 수를 구하는 문제이다. 단순히 수를 모두 이어붙혀 문자열을 만들고 문자열의 k번째 수를 출력하면 될거 같지만 n이 최대 1억개라 이어붙이는 과정에서 메모리 초과가 발생한다. 그래서 실제로 이어붙이는 것이 아닌 '탐색'을 해야 한다. 

 

몇 번째 수를 구하는 문제이니 '자릿수'가 중요하다. 

 

한 자리수 : 9개 ➟ 9개

두 자리수 : 90개 ➟ 90*2 ➟ 180개  

세 자리수 : 900개 ➟ 900*3 ➟ 2700개

 

문제는 몇번째 수를 구하는 것이니 수의 개수 x 자릿수를 해야 한다. 

 

200번째 수를 구한다고 가정해보자. 

 

한 자리수 + 두 자리수는 189번째까지이다. 200번째 - 189번째 = 11번째

11번째가 남았다. 자릿수는 3자리이다. 

 

100 101 102 103 104 ...

 

11을 3으로 나누면 몫은 3이고 나머지는 2이다. 몫이 3이니 100, 101, 102까지이다. 그리고 나머지 2이니 2번째를 의미한다. 103의 두번째 수는 0이다.  0이 200번째 수이다.  결과는 나왔지만 이를 코드로 구현하려면 약간의 변형이 필요하다. 

 

 

 

세 자리수에서 첫 번째 수는 100이 아니라 101이어야 한다. 한 자리수에서 첫 번째 수가 1이므로 세자리 수에서 첫 번째수는 101이어야 한다.  

 

 

그리고 11을 3으로 나누지 말고 11에서 '-1'을 한 10을 3으로 나누어야 한다. 

 

11을 3으로 나누면 

나머지 1 : 1

나머지 2 : 0

나머지 0 : 3

 

10을 3으로 나누면

 

나머지1 : 0

나머지2 : 1

나머지3 : 2

 

0,1,2 포지션이 인덱스와 일치한다. 

 

103 =  99 + 1 + (11-1)//3 

(11-1)%3 == 0 이면 1

(11-1)%3 == 1 이면 0

(11-1)%3 == 2 이면 3 이다.

 

( 수학적 센스가 필요해 보인다.... )

 

◎ 코드

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

start = 0
digit = 1 #자릿수
nine = 9 

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

result = (start+1) + (k-1)//digit 

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