7262 : 격자 이분탐색
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N \times M$ 크기의 격자에 정수 값이 채워져 있습니다. 기준 값 $T$가 주어질 때, 격자에서 $T$ 이하인 값을 가진 셀의 수를 구하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 격자 크기 $N$, $M$이 주어집니다. ($1 \le N, M \le 500$)
둘째 줄부터 $N$개의 줄에 격자 값이 주어집니다.
마지막 줄에 기준 값 $T$가 주어집니다.
둘째 줄부터 $N$개의 줄에 격자 값이 주어집니다.
마지막 줄에 기준 값 $T$가 주어집니다.
출력 설명
격자에서 값이 $T$ 이하인 셀의 수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
1 2 3
4 5 6
7 8 9
5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5도움
각 셀을 순회하며 값이 $T$ 이하인 셀을 세면 $O(NM)$에 해결할 수 있습니다. 각 행이 정렬되어 있다면 이분탐색으로 $O(N \log M)$에도 해결할 수 있습니다.