[Python] BOJ 1300. k번째 수

www.acmicpc.net/problem/1300

 

1300번: K번째 수

 

---

문제 예제 해석

A : 3x3

	1	2	3
1	1	2	3
2	2	4	6
3	3	6	9

 

B : len(B) = 9 = 3x3

1

2

2

3

3

4

6

6

9

 

출력값 : B[7] = 6

 

- 임의의 숫자 m을 골라서 k번째 숫자인지 판단해보는 문제

- m을 이분 탐색으로 찾아보자 : m은 O(logK)

- m보다 작은 숫자의 개수를 어떻게 하면 빠르게 구할 수 있는가

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

   - 따라서 min(mid/i, N)이 i번째 행에서 mid보다 작은(= 임의의 m보다 작은)숫자들의 개수가 됨

- 따라서 각 O(logK)에 대해, 1부터 N까지 모든 i행에 대해 m/i를 수행해주어야 하므로 총 시간 복잡도는 O(NlogK) 

 

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

while start <= end:
    mid = (start + end) // 2
    tmp = 0
    for i in range(1, N+1) :
        tmp += min(mid // i, N)
    if tmp >= K:
        ans = mid
        end = mid - 1
    else:
        start = mid + 1
print(ans)