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

4. 1300 K번째 수

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)