부울행렬의 부울곱
시간 제한2초메모리 제한512 MB
두 N x N 0/1 행렬의 불리언 곱을 구하고 결과 행렬에서 1의 개수를 센다.
문제
문제를 출제하던 욱제는 갑자기 괴랄한 문제를 내고 싶어졌다. 불행히도 이번 대회에는 프로그래밍을 막 시작한 참가자가 많아서 그럴 수는 없었다. 그래도 욱제는 신입생을 괴롭히고 싶은 욕망을 버리지 못했다.
"하하! 과연 신입생들이 이 문제를 풀 수 있을까?"
문제는 간단하다. 0과 1로만 이루어진 크기의 부울행렬 와 가 주어진다. 두 행렬의 부울곱 를 구했을 때 에 있는 1의 개수를 세면 된다. 부울곱은 다음과 같이 계산한다.
는 행렬 의 행 열 원소이고, 는 논리곱(AND), 는 논리합(OR)이다. 자, 어서 코딩하자!
입력
첫째 줄에 행렬의 크기 ()이 주어진다. 다음 개의 줄에 부울행렬 가, 그다음 개의 줄에 부울행렬 가 주어진다. 각 줄에는 0 또는 1인 정수 개가 공백으로 구분되어 주어진다.
출력
와 의 부울곱인 행렬 에 있는 1의 개수를 출력한다.
힌트
예제 1의 부울곱 결과는 다음과 같다.
1 1 1
1 1 1
0 0 1
따라서 1의 개수는 7이다.
예제 2의 부울곱 결과는 다음과 같다.
0 0
1 1
따라서 1의 개수는 2이다.