부울행렬의 부울곱

시간 제한2초메모리 제한512 MB

요약
두 N x N 0/1 행렬의 불리언 곱을 구하고 결과 행렬에서 1의 개수를 센다.
난이도

보통10점 중 4점

유형
행렬, 완전 탐색, 비트 연산
정답자
아직 제출이 없습니다

문제

문제를 출제하던 욱제는 갑자기 괴랄한 문제를 내고 싶어졌다. 불행히도 이번 대회에는 프로그래밍을 막 시작한 참가자가 많아서 그럴 수는 없었다. 그래도 욱제는 신입생을 괴롭히고 싶은 욕망을 버리지 못했다.

"하하! 과연 신입생들이 이 문제를 풀 수 있을까?"

문제는 간단하다. 0과 1로만 이루어진 N×NN \times N 크기의 부울행렬 A=[aij]A=[a_{ij}]와 B=[bij]B=[b_{ij}]가 주어진다. 두 행렬의 부울곱 C=[cij]C=[c_{ij}]를 구했을 때 CC에 있는 1의 개수를 세면 된다. 부울곱은 다음과 같이 계산한다.

cij=(ai1∧b1j)∨(ai2∧b2j)∨⋯∨(ain∧bnj)c_{ij} = (a_{i1} \land b_{1j}) \lor (a_{i2} \land b_{2j}) \lor \cdots \lor (a_{in} \land b_{nj})

xijx_{ij}는 행렬 XX의 ii행 jj열 원소이고, ∧\land는 논리곱(AND), ∨\lor는 논리합(OR)이다. 자, 어서 코딩하자!

입력

첫째 줄에 행렬의 크기 NN(1≤N≤3001 \le N \le 300)이 주어진다. 다음 NN개의 줄에 부울행렬 AA가, 그다음 NN개의 줄에 부울행렬 BB가 주어진다. 각 줄에는 0 또는 1인 정수 NN개가 공백으로 구분되어 주어진다.

출력

AA와 BB의 부울곱인 행렬 CC에 있는 1의 개수를 출력한다.

힌트

예제 1의 부울곱 결과는 다음과 같다.

1 1 1
1 1 1
0 0 1

따라서 1의 개수는 7이다.

예제 2의 부울곱 결과는 다음과 같다.

0 0
1 1

따라서 1의 개수는 2이다.

예제2

  1. 예제 1

    입력
    3
    1 1 0
    0 1 0
    0 0 1
    1 0 0
    1 1 1
    0 0 1
    
    예상 출력
    7
    
  2. 예제 2

    입력
    2
    0 1
    1 1
    1 1
    0 0
    
    예상 출력
    2