[Baekjoon] 1300번 : K번째 수 (Python, 이분 탐색)

Python

방법 1 - 메모리 30840KB / 시간 1040ms / 코드 길이 254B

이분 탐색는 선정이 중요하다.

무엇을 start, end, mid로 놓을 것인가 (이때의 list는 오름차순으로 정렬가능한 리스트여야 한다.)

무엇을 조건으로 값과 비교할 것인가

본 문제에서 start, end, mid는 1~n*n에 해당하는 value로 선정한다.

그리고 조건에 해당하는 cnt는 value보다 작은 것들의 개수를 의미한다.

고로 각각의 value에 대해 작은 것들의 개수를 cnt에 저장하여 이를 기반으로 k와 비교해서 start와 end를 재설정한다.

그렇다면 value보다 작은 것들의 개수는 어떻게 셀 것인가

그것은 mid에서 i번째 행에 해당하는 숫자를 나눠서 그 개수를 조사한다. 단 해당 숫자가 n보다 크다면 n을 출력한다.

min(mid//i, n)

	1열	2열	3열
1행	1	2	3
2행	2	4	6
3행	3	6	9

예를 들어 mid에 해당하는 value가 라고 가정해보겠다. 즉, 이말은 위 행렬에서 4보다 작거나 같은 개수가 몇 개 있니를 앞으로 구해야 한다.

각 행렬의 value는 ixj에 해당하기 때문에 행을 기준으로 value를 나눈다.

4//1 = 4

4//2 = 2

4//3 = 1

이때, 4는 3보다 크므로 열의 최대값인 n으로 수정한다.

이 결과 3+2+1 = 6의 값을 가진다.

즉, 6이라는 값은 위 표에서 4라는 value보다 작거나 같은 개수가 총 6개라는 뜻이다.

우리는 k=7번째의 값을 구하고 싶기 때문에 4보다는 커야하고 이에 따라 조건을 설정한다.(start = mid + 1)

start, end = 5,7이 설정된다.

mid = 6

6보다 작거나 같은 개수를 구하기 위해 for문을 돌리면

6//1 = 6

6//2 = 3

6//3 = 2

3+3+2 = 8

즉, A라는 행렬에서 6보다 작거나 같은 개수는 총 8개있다.

이런 식으로 이분 탐색을 진행하다보면 최종적인 값을 얻을 수 있다.

n = int(input())
k = int(input())
start, end = 1, k

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