백준 3321 가장 큰 직사각형

 

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

3321번: 가장 큰 직사각형

n개의 행 각각에 대해 그 행을 밑변으로 하는 직사각형을 확인하면 된다. 

 

각 행에서 각 위치에 대해 위로 연속한 1의 개수를 위 행에서의 값을 참조하여 O(m)만에 update할 수 있다.

대충 아래와 같은 그림을 생각해 보면 되겠다. 

 

 

이 연속한 1의 개수를 내림차순으로 정렬하면, 그 행을 밑변으로 하는 직사각형 중 가장 큰걸 쉽게 확인할 수 있다. TC의 답을 나타낸 아래 그림과 같이, 내림차순인 히스토그램에서 가장 큰 직사각형을 구하는 것이기 때문이다. 

 

그리고 연속한 개수가 1 증가하거나 0으로 바뀌거나 둘 중 하나기에, 0으로 바뀐건 뒤쪽으로 몰아 놓으면 1이 증가하는 부분은 위 행에서의 정렬 상태가 유지되어 O(m)만에 정렬까지 처리된다. O(mlogm)으로 정렬하면 터진다. 

0.6초라서 상수가 크게 짜면 O(nm)짜리 풀이긴 하지만 TLE가 날 수 있음에 주의하자. 필자는 592ms로 통과했다.