우당탕탕 영화예매

면접 대비

시간 제한1초메모리 제한1024 MB

요약

'1'로 표시된 예약 좌석을 제외하고, 한 가로줄에서 연속된 빈 좌석 K개를 잡는 방법의 수를 구합니다.

난이도: 쉬움10점 중 3점
유형: 배열, 슬라이딩 윈도우
정답자: 아직 제출이 없습니다

문제

도은이는 동아리 문화의 날을 맞아 동아리원들과 함께 영화를 보기로 했다. 영화관 좌석은 $M$ 행 $N$ 열의 직사각형 모양으로 배치되어 있다. 도은이는 동아리원의 유대감을 중요하게 여겨서, 이미 예매된 좌석을 피해 동아리원 모두가 가로로 이어서 앉을 수 있도록 좌석을 예매하고 싶어 한다. 도은이를 도와 모든 동아리원이 가로로 이어서 앉을 수 있도록 예매하는 경우의 수를 구해보자. 다만 예매한 좌석은 같고 각 사람이 앉는 위치만 바뀌는 경우는 한 가지로 본다.

입력

첫째 줄에 영화관 세로줄의 개수 $N$ ( $1 \leq N \leq 1\,000$ ), 가로줄의 개수 $M$ ( $1 \leq M \leq 5\,000$ ), 영화를 관람할 동아리원의 수 $K$ ( $1 \leq K \leq 10$ )가 주어진다.

둘째 줄부터 $N$ 개의 줄에 걸쳐 $i$ 번째 줄에는 $i$ 번째 열의 좌석 예매 현황이 길이 $M$ 인 문자열 $s_i$ 로 주어진다. $s_i$ 의 $j$ 번째 문자는 $i$ 열 $j$ 번째 좌석의 예매 현황을 나타낸다. 이 문자가 '0'이면 예매 가능한 빈 좌석이고, '1'이면 예매가 완료되어 예매할 수 없는 좌석이다.

출력

동아리원들이 모두 가로로 이어서 앉을 수 있도록 영화를 예매하는 경우의 수를 출력한다. 문제의 조건에 맞게 영화를 예매할 방법이 없다면 $0$ 을 출력한다.

예제2

예제 1
입력
```
3 5 3
11000
01010
10000
```
예상 출력
```
3
```
예제 2
입력
```
3 4 3
1101
1001
0101
```
예상 출력
```
0
```