[백준] 1300번 : K번째 수

1300번: K번째 수

해당 문제는 이분탐색문제로 문제의 정답을 찾는데에 고민이 많았다.

문제의 핵심은 K번째 수를 구해야하는 것이고, 숫자의 규칙을 잘 파악하여 K번째수가 몇인지 찾아야한다.

배열의 크기가 매우 크기때문에 메모리에 넣고 정렬을 하여 구하는 알고리즘은 바람직 하지 않다.

문제 풀이의 아이디어는 다음과 같습니다

특정한 숫자를 정하고, a[i][j]를 모두 순회하면서 자기자신보다 큰 값을 찾습니다. 샌 개수가 많다는것은 값이 더 커야 다음에 순회하였을때 개수가 줄어들 것이고, 샌 갯수가 적다는것은 자기자신의 숫자를 낮추어야 갯수가 작아지므로 이분으로 범위를 좁혀가며 정답을 찾습니다.

여기서 더 시간복잡도를 줄일 수 있는 방법은 나누기 연산을 수행하는것입니다.

예를들어 i가 1일때 j 1,2,3,4,5,6,7,8,9 일때를 보면 내가 K숫자라면 K//i로 개수를 빠르게 탐색 할 수 있습니다.

import sys

N = int(sys.stdin.readline())
k = int(sys.stdin.readline())

start = 1
end = k
ansnwer = 0
while start <= end:
    mid = (start+end) // 2
    count = 0
    for i in range(1, N+1):
        count += min(mid//i, N)

    if count >= k:
        ansnwer = mid
        end = mid-1
    else:
        start = mid+1

print(ansnwer)