[Algorithm][BOJ]1300번 - K번째 수(Python)

👇문제 링크👇
boj_1300

💡 문제요약

• A[i][j] = i * j (A는 2차원 배열)
• B : 1차원배열
• A의 요소들을 B에 넣고 B를 오름차순 정렬

💡 문제해결

• 이진탐색을 활용한다.

💻 Code

N = int(input())
k = int(input())

left = 1 
right = k
ans = 0

while left <= right:
  count = 0
  mid = (left+right)//2
  
  for i in range(1, N+1):
    count += min(mid//i, N)
  if(count < k):
    left = mid + 1
  else:
    ans = mid
    right = mid -1
print(ans)

💡 후기

• 이진탐색의 시간복잡도 : O(logN)
  • 데이터가 정렬된 배열에서 특정한 값을 찾아낼 때!
  • 효율적인 탐색이 가능해 많이 사용된다.
  • 이진탐색은 이 문제가 이진탐색으로 푸는건지.. 생각해 내는게 어렵다.

앞으로 열심히 기록하는게 저의 목표입니당👍