[BOJ 15479] L番目のK番目の数 (LthKthNumber)

문제: https://www.acmicpc.net/problem/15479

문제 요약: $A$의 연속된 부분수열 중 길이가 $K$ 이상인 모든 부분수열을 구하고, 그 수열의 (작은 순으로) $K$ 번째 수를 구합니다. 그 수를 모두 모았을 때 $L$ 번째 수를 구합니다.

풀이:

$A$의 모든 값이 $0$이나 $1$인 경우 $L$ 번째 수를 구하기 위해서는 $K$ 번째 수가 $0$인 구간의 수를 세면 됩니다. $K$ 번째 수가 $0$이라는 것은 수열에서 $0$이 $K$ 개 이상 있다는 의미입니다.

이는 two-pointer를 사용하면 쉽게 구할 수 있습니다.

원래 문제를 결정문제로 바꾸기 위해서 parametric search를 사용하면 문제를 해결할 수 있습니다.

 

코드: https://www.acmicpc.net/source/share/819ba475afa242bd9d07fe029135e052