[백준] 1300번 - K번째 수 (파이썬)

https://www.acmicpc.net/problem/1300

# K번째 수
N = int(input())
k = int(input())

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

print(result)

 

이진탐색

B리스트는 정렬된 상태라고 문제에 적혀져있다. 이분탐색을 사용

B[k]는 항상 k보다 작거나 같기 때문에 end를 k로 지정해준다.

1. start가 end보다 작거나 같을 동안 이진 탐색 수행

    - count : mid보다 작은 수들의 개수

    - 해당 열에서 X보다 작은 수의 개수는 X를 해당 열의개수(1~N)으로 나눈값 (단, N보다 커질 수 없음)

2. count == k 이면 result를 출력

 

아 좀 많이 해맸다... 이진탐색도 약점이라 결국 풀이 아이디어를 살짝 보고야 말았다