Problem Solving
[BOJ1300] K번째 수 (이분 탐색)
dododoo
2020. 3. 23. 13:40
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