BOJ 7783

 

https://www.acmicpc.net/problem/7783

 

코드

http://boj.kr/3bb472b769d84eae85fb645da11bbf8d

 

KBTU Open 2008 B

 

난이도 : P2

 

Elapse Time : 30min

 

우선 직사각형 2개를 골랐을 경우 어떤 이유에서든 각 직사각형은 상하좌우로 확장될 수 없다는 것을 먼저 생각했다. 그 후에는 먼저 직사각형 1개에 대해 가장 큰 직사각형을 구하는 방법에 대해 고민했다. 고민을 하던 중 행렬의 한 행을 bitset으로 저장해 놓으면 어떻게 될지 생각을 해보았다. 어떤 직사각형이 $i$번째 행부터 $j$번째 행까지 걸쳐있다고 할 때 $i$번째 행부터 $j$번째 행까지 bitwise or 연산을 해주었을 때 0인 열에만 직사각형이 존재 가능하다. $M$의 제한이 200이기 때문에 모든 $i$, $j$에 대해서 연속하는 0의 최대 길이를 계산하여 최대 면적을 구하면 $O(NM^2)$에 계산 가능하다. 이를 2개를 계산하는 것으로 확장할 생각을 해보았는데 두 직사각형에 겹치는 행이 없다면 prefix max와 suffix max를 미리 계산해 놓고 최대 면적 합을 쉽게 구할 수 있지만 두 직사각형이 같은 행을 공유하는 경우가 문제였다. 하지만 두 직사각형이 겹치지 않고 같은 행을 공유한다면 같은 열을 공유할 수는 없으므로 열에 대해서도 같은 방식으로 prefix max와 suffix max을 계산해 놓으면 모든 경우를 커버할 수 있고 이를 구현해 해결하였다.