이것도 해결해 보시지
시간 제한5초메모리 제한512 MB
N x L 행렬에서 3N열 구간을 A, B, C 세 개의 N x N 행렬로 나눠 A*B=C가 성립하는 구간들을 서로 겹치지 않게 골라 칠한 칸 수의 최댓값을 구한다.
문제
크기의 정수 행렬 이 있다. 에서 연속한 열 개를 고른 뒤 왼쪽부터 열씩 끊으면 행렬 세 개가 나온다. 이를 순서대로 , , 라고 하자. 가 성립하면 이 구역을 색칠할 수 있다.
색칠하려는 구역에 이미 색칠된 칸이 하나라도 있으면 그 구역은 색칠할 수 없다. 순서를 적당히 정해 색칠할 때, 칠할 수 있는 숫자의 최대 개수를 구하라.
입력
첫째 줄에 정수 과 이 주어진다. (, )
다음 개의 줄에는 행렬 의 각 행이 주어진다. 번째 줄의 번째 정수가 이다. ()
출력
칠할 수 있는 숫자의 최대 개수를 출력한다.