[Python] 백준 1300번 : K번째 수

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

1300번: K번째 수

---

💡 문제 풀이

이분 탐색 문제이다.

 

메모리가 128MB까지고 배열의 크기가 100억이 될 수 있어서 반복문으로 메모리를 할당해서 풀 수 없다.

찾으려는 값 K보다 작은 값의 개수를 알면 K가 어디 있는지 알 수 있기 때문에

확인하는 값(mid)보다 작거나 같은 숫자를 세면서 이분 탐색을 진행해주면 된다.

✔️ 느낀 점

이분 탐색 문제는 풀면서 항상 느낀다. 아이디어를 통해서 접근하는게 중요하다고. 메모리 관련해서 아이디어를 생각해내지 못해서 내 힘으로 온전히 풀어내지 못한 것 같다.

💻 코드

import sys

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

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:
        ans = mid
        right = mid - 1
    else: 
        left = mid + 1
    
print(ans)