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

dek1313·2020년 5월 23일
0
post-thumbnail

👇문제 링크👇
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)
    • 데이터가 정렬된 배열에서 특정한 값을 찾아낼 때!
    • 효율적인 탐색이 가능해 많이 사용된다.
    • 이진탐색은 이 문제가 이진탐색으로 푸는건지.. 생각해 내는게 어렵다.

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

profile
닭발먹고 힘내서 복습하자👻

0개의 댓글