[Algorithm 풀이] NN단표

본 문제는 이진탐색 알고리즘 대표 문제이다! 😀

문제

NN은 2차원 배열의 모양으로 곱셈 1단부터 N단 까지 값을 적어놓은 형태. 

토리는 구구단표처럼 NN단표를 만들었다고 한다.

NN단표는 2차원 배열의 모양으로 곱셈 1단부터 N단까지의 값들을 적어놓은 형태이다.

NN단표의 배열을 A라고 했을 때, 배열의 들어가는 수 A[i][j]=i*j이다.(즉, 4행 7열에는 28, 7행 5열에는 35가 들어가 있다.)

알랩이는 N단까지 나온 숫자들 중에서 K번째로 작은 수를 찾고 싶어한다.

이때, 중복되는 여러 수들을 고려한다. 즉 N*N개의 모든 수들 중에서 K번째 수를 구하는 것이다.

---

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄에 K가 주어진다. K는 N*N보다 작거나 같은 자연수이다.

출력

K번째 원소를 출력한다.

---

코드

n = int(input()) 
k = int(input()) #k번째 요소 출력

def binarySearch(x):
  result = 0
  for i in range(1, n+1):
    if (i * n) < x: # 맨 마지막 숫자가 작으면
      result += n
    else:
      if x % i == 0 :
        result += (x//i)-1
      else:
        result += x//i
  return result+1
start = 1
end = n * n +1
while(start+1 < end): #두개가 붙어 있으면 #e.g.12 13
#start : 항상 k번째 보다 작거나 같은 순서를 가지는 숫자
#end : 항상 정답이 되는 숫자보다 큰 숫자
  mid = (start + end) // 2
  myorder = binarySearch(mid) #이진탐색
  if myorder <= k:
    start = mid
  else:
    end = mid
print(start)