백준14492 부울행렬의 부울곱

작성일 | In

문제 링크

  • http://icpc.me/14492

문제 출처

  • 2017 선린 봄맞이 대회 F번

시간복잡도

  • O(n3)

풀이

이 문제의 출제 의도는 주어진 수식을 코드로 옮기는 능력을 보는 것이라고 출제자 분께서 말씀하셨습니다.

c[i][j]는 (a[i][1] and b[1][j]), (a[i][2] and b[2][j]), … , (a[i][n] and b[n][j]) 총 n개의 항을 모두 or연산한 값입니다.
코드로 옮기면 c[i][j] |= a[i][k] & b[k][j] (단, 1 <= k <= n) 로 나타낼 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>

int main(){
	int n;
	int arr1[310][310]={0}, arr2[310][310]={0}, arr3[310][310]={0};
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			scanf("%d", &arr1[i][j]);
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			scanf("%d", &arr2[i][j]);
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			for(int k=0; k<n; k++){
				arr3[i][j]|=arr1[i][k]&arr2[k][j];
			}
		}
	}
	int cnt=0;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(arr3[i][j]) cnt++;
		}
	}
	printf("%d", cnt);
}