[BOJ 3321] 가장 큰 직사각형

View as PDF

Submit solution

Points: 4
Time limit: 0.6s
Memory limit: 128M

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

0과 1로 이루어진 N * M 행렬이 주어졌을 때, 1로 이루어진 가장 큰 직사각형을 찾는 프로그램을 작성하시오. 직사각형은 전체가 1로 가득 차있어야 한다. 또한, 열을 순서를 바꿀 수 있다.

입력 형식

첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 행렬이 주어진다.

출력 형식

첫째 줄에 가장 큰 직사각형의 넓이를 출력한다.

예제 입력

10 6
001010
111110
011110
111110
011110
111111
110111
110111
000101
010101

예제 출력

21

힌트

열의 순서를 적절히 바꿔, 2열, 4열, 5열이 서로 붙어있게 놓는다면, 크기가 21인 직사각형을 얻을 수 있다. (2행~8행 * 2,4,5열)


Comments

There are no comments at the moment.