7258 : 행렬 이분탐색
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
행과 열이 모두 오름차순으로 정렬된 $N \times M$ 행렬이 주어질 때, $K$번째로 작은 원소의 값을 구하십시오.
이분탐색으로 값을 탐색하고, 각 값에 대해 행렬 내 해당 값 이하인 원소의 수를 세어 검증합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
이분탐색으로 값을 탐색하고, 각 값에 대해 행렬 내 해당 값 이하인 원소의 수를 세어 검증합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 행렬의 크기 $N$, $M$과 찾을 순위 $K$가 주어집니다. ($1 \le N, M \le 300$, $1 \le K \le N \times M$)
둘째 줄부터 $N$개의 줄에 각 행의 원소들이 공백으로 구분되어 주어집니다.
둘째 줄부터 $N$개의 줄에 각 행의 원소들이 공백으로 구분되어 주어집니다.
출력 설명
행렬에서 $K$번째로 작은 원소의 값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3 5
1 5 9
10 11 13
12 13 15
출력 예시
COPY
복사되었습니다!
복사되었습니다!
11도움
이분탐색 범위: 최솟값부터 최댓값. 검사 함수: 값 $m$ 이하인 원소의 수가 $K$ 이상인지 확인합니다. 각 행은 정렬되어 있으므로
bisect_right로 $O(N \log M)$에 셀 수 있습니다.