[BOJ1300] K번째 수 (이분 탐색)

1. 문제

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

2. Note

파라매트릭 서치 문제임을 알고 풀었는데도 어떤 수보다 작은(혹은 작거나 같은) 수의 개수를 찾아내는 함수를 떠올리지 못했다.

2.1. 이분 탐색에서 right를 k로 잡아도 충분한 이유

좀 더 고민해 보아야 할 것 같다. 잘 모르겠어어서 right 초깃값을 n*n (최악의 경우 1e10)로 잡고 풀었다.

2.2. 이분 탐색으로 구한 값이 행렬 내에 실제로 존재하는가

최솟값을 구하면 그 값은 행렬 내에 존재하는 것이 명백함

2.3. Parametric Search

(1) 함수를 만들어 봅니다.
(2) 이것이 항상 증가, 혹은 항상 감소하는 것인지 따져봅니다.
(3) 만약 그렇다면 반씩 쪼개서 풀어봅니다.
- BOJ chogahui05

3. Reference

https://www.acmicpc.net/board/view/14272