백준 1300번 "K번째 수"

문제

백준 1300번 K번째 수

풀이

처음 문제를 보고선 바로 반복문 두개 돌려서 2차원 배열만들고 오름차순으로 정렬해서 문제풀었는데, 메모리 초과가 뜨더라....

여튼 이런 방식이 너무나도 비효율적이란 걸 깨닫고 검색 좀 해보니깐 이 문제도 이분탐색 문제였다.

1차원 배열을 오름차순으로 놓고 x라는 수를 찾는다면 x의 인덱스는 x보다 작거나 같은 수들 다음에 위치할 것이다.
즉, x보다 작거나 같은 숫자를 전부 찾아주면 x의 위치를 알 수가 있다.

5*5 크기의 배열을 하나 그려놓고 생각해보자.
찾으려는 수 x가 12일 때, 각 행마다 12보다 적은 수는 12/행인덱스의 몫(열의 최대 크기가 5이므로 5가 넘는 경우는 5여야 한다)이라는 것을 알 수 있다.
이를 이용해 이분탐색을 진행하면서 특정 mid값의 인덱스가 주어진 k값과 같아질 때를 찾으면 된다.

Python 코드

import sys
input = sys.stdin.readline

n = int(input())
k = int(input())
left, right = 1, k

while left <= right:
  mid = (left + right) // 2
  tmp = 0

  for i in range(1, n+1):
    tmp += min(mid//i, n)

  if tmp >= k:
    ans = mid
    right = mid -1
  else:
    left = mid + 1

print(ans)