알고리즘

백준 - 1300 K번째 수 [이분탐색]

ghtis1798 2021. 8. 9. 06:24

4. 1300 K번째 수

image

4.1. 문제유형

  • Binary Search

4.2. 자료구조

  • left (int): 각 행의 최소값 인덱스 == 1
  • right (int): 각 행의 최대값 인덱스 == n
  • mid (int): (left+right)//2 == 중간값으로 탐색해 나갈 값

4.3. 해결과정

  • 핵심 아이디어는 행별로 mid값보다 작은 값의 개수를 세는 것이다.
  • 각 행의 값은 i의 배수이며 작은 값들의 개수는 최대 n, 최소 mid // i이다.
  1. left <= right 동안 mid를 계산 후 n행에 대해 mid보다 작은 개수를 구한다.
  2. mid보다 작은 개수가 k와 같거나 크면 answer = mid 후 right = mid - 1 (더 작은 좌측탐색)
  3. mid보다 작은 개수가 k보다 클 경우 left = mid + 1 (더 큰 우측탐색)
  4. 반복문 종료후 answer를 출력한다.
n = int(input())
k = int(input())
cnt, answer = 0, 0
left, right = 1, k

while left <= right:
    mid = (left + right)//2
    cnt = 0
    for i in range(1, n+1):
        cnt += min(mid // i, n)
    if cnt >= k:
        answer = mid
        right = mid - 1
    else:
        left = mid + 1
print(answer)