5.넓은 방

문제:

풀이:

주석으로는 설명이 부족한 것 같아 덧붙이자면 입력 행렬 matrix를 받고 이 행렬에서 0이 오른쪽으로 몇개 연속되는지를 나타내는 행렬 matrix2를 새로 만든다.

matrix2에서 각 원소의 값은 matrix에서 해당 인덱스의 원소 포함 오른쪽으로 0인 원소가 몇개인지를 나타내므로

matrix2(i, j)=n이라고 할때 matrix2(i+1, j)가 n보다 크거나 같다면 i+1번째 행을 포함하는 가로가 n인 직사각형을 만들 수 있다는 뜻이다.

이런 점을 이용해서 matrix2의 모든 원소에서 자신보다 크거나 같은 원소가 아랫쪽으로 몇개가 연속되는지 구하고 그 갯수*자신의 값 n을 해서 직사각형의 넓이를 구하고 그 최대값을 출력하는 방식이다.

#-*-incoding:utf-8-*-
#python

import sys

def count_zero (arr, j, width, cnt): #행에서 연속되는 0의 갯수를 찾아주는 함수
        if j==width-1: #마지막 원소일경우 
                return cnt
        if arr[j+1]==0:
                return count_zero(arr, j+1, width, cnt+1)
        else:
                return cnt


def count_num (matrix, i, j, height, cnt, num): #같은열 아래에 자신보다 큰 숫자가 몇개 연속되는지 반환
        if i == height-1:
                return cnt
        if matrix[i+1][j]>=num:
                return count_num(matrix, i+1, j, height, cnt+1, num)
        else:
                return cnt

size=raw_input().split()

height=int(size[0])
width=int(size[1])

matrix=[[0 for col in range (width)] for row in range (height)] #입력받을 행렬
matrix2=[[0 for col in range (width)] for row in range (height)] #0이 연속되는 갯수를 저장할 행렬

for i in range (height): #입력행렬을 받는 부분
        arr=sys.stdin.readline().split()
        for j in range (width):
                matrix[i][j]=int(arr[j])
                
for i in range (height): #입력행렬에서 자신으로부터 오른쪽으로 0이 연속되는 갯수를 matrix2에 저장
        for j in range (width):
                if matrix[i][j] == 0:
                        matrix2[i][j]=count_zero(matrix[i], j, width, 1)


max_size=0
for j in range (width):
        for i in range (height):
                tmp=count_num(matrix2, i, j, height, 1, matrix2[i][j]) #tmp: 사각형의 높이, matrix2[i][j]: 넓이
                if tmp*matrix2[i][j] > max_size:
                        max_size = tmp*matrix2[i][j]

print max_size