[BinarySearch] K번째 수 1300번

wookje.dance/2017/02/20/boj-1300-K%EB%B2%88%EC%A7%B8-%EC%88%98/

[BOJ] 1300 : K번째 수

N = 4일 때

배열 A =

[1, 2, 3, 4]
[2, 4, 6, 8]
[3, 6, 9, 12]
[4, 8, 12, 16]

 

풀이

임의의 숫자 m을 골라서 K번째 숫자인지 판단해보자!

그 임의의 숫자 m은 무려 O(log K)에! 무려 이분 탐색으로 찾아보자!

그렇다면 떠오르는 질문, m 보다 작은 숫자의 개수를 어떻게 하면 빠르게 구할 수 있을까?

A[i][j]에서, i행에 속한 숫자들은 i*j이므로 모두 i의 배수이다.

그러므로 min(mid/i, N)이 i번째 행에서 mid보다 작은(= 임의의 m보다 작은) 숫자들의 개수가 된다.

eg. N = 1000인 경우, 첫 mid가 1000*1000/2 = 50만이 되는데, 50만/i가 N을 넘어갈 수 있으므로 min(mid/i, N)을 해준다.

조금 더 쉽게 쓰자면, i행의 숫자들은 i*1, i*2, i*3, ..., i*N으로 구성되어 있다. i행의 숫자들 중 m보다 작거나 같은 숫자는 (i*j <= m)를 만족하는 j의 개수이고 이는 i*1, i*2, ..., i*j이므로, m/i와 같은 값이 된다.

각 O(log K)에 대해, 1부터 N까지 모든 i행에 대해 m/i를 수행해주어야 하므로

총 시간 복잡도는 O(NlogK)가 된다.

 

N, K = int(input()), int(input())
start, end = 1, K

while start <= end:
    mid = (start + end) // 2
    
    temp = 0
    for i in range(1, N+1):
        temp += min(mid//i, N) #mid 이하의 i의 배수 or 최대 N
        
    
    if temp >= K: #이분탐색 실행
        answer = mid
        end = mid - 1
    else:
        start = mid + 1
print(answer)