문제

세준이는 NM크기로 직사각형에 수를 NM개 써놓았다.

세준이는 이 직사각형을 겹치지 않는 3개의 작은 직사각형으로 나누려고 한다. 각각의 칸은 단 하나의 작은 직사각형에 포함되어야 하고, 각각의 작은 직사각형은 적어도 하나의 숫자를 포함해야 한다.

어떤 작은 직사각형의 합은 그 속에 있는 수의 합이다. 입력으로 주어진 직사각형을 3개의 작은 직사각형으로 나누었을 때, 각각의 작은 직사각형의 합의 곱을 최대로 하는 프로그램을 작성하시오.

# 1451
import sys
input = lambda: sys.stdin.readline().strip()

# 1.     2.     3.     4.     5.       6.
# 1/1    1/1    111    1/1    1/1/1    111
# ///    //1    ///    1//    1/1/1    111
# 111    1/1    1/1    1/1    1/1/1    111
# 4가지 경우로 나누기 (가로 > 1, 세로 > 1)
# 가장 작은 직사각형 : y*x

n, m = map(int, input().split())
arr = []
for _ in range(n):
    string = list(input())
    str_arr = []
    for st in string:
        str_arr.append(int(st))
    arr.append(str_arr)
    

sum_arr = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        sum_arr[i][j] = arr[i-1][j-1] + sum_arr[i-1][j] + sum_arr[i][j-1] - sum_arr[i-1][j-1]

max_num = 0
if n == 1:
    for i in range(1, m-1):
        for j in range(i+1, m):
            num1 = sum_arr[1][i] - sum_arr[1][0]
            num2 = sum_arr[1][j] - sum_arr[1][i]
            num3 = sum_arr[1][m] - sum_arr[1][j]
            
            num = num1 * num2 * num3
            max_num = max(max_num, num)
            
elif m == 1:
    for i in range(1, n-1):
        for j in range(i+1, n):
            num1 = sum_arr[i][1] - sum_arr[0][1]
            num2 = sum_arr[j][1] - sum_arr[i][1]
            num3 = sum_arr[n][1] - sum_arr[j][1]
            
            num = num1 * num2 * num3
            max_num = max(max_num, num)
            
else:
    # 1.
    for i in range(1, n):
        for j in range(1, m):
            num1 = sum_arr[i][j] - sum_arr[0][0]
            num2 = sum_arr[i][m] - sum_arr[i][j]
            num3 = sum_arr[n][m] - sum_arr[i][m]
            
            num = num1 * num2 * num3
            max_num = max(max_num, num)
            
    # 2.
    for i in range(1, n):
        for j in range(1, m):
            num1 = sum_arr[i][j] - sum_arr[0][0]
            num2 = sum_arr[n][m] - sum_arr[n][j]
            num3 = sum_arr[n][j] - sum_arr[i][j]
            
            num = num1 * num2 * num3
            max_num = max(max_num, num)
            
    # 3.
    for i in range(1, n):
        for j in range(1, m):
            num1 = sum_arr[i][m] - sum_arr[0][0]
            num2 = sum_arr[n][j] - sum_arr[i][j]
            num3 = sum_arr[n][m] - sum_arr[i][m] - sum_arr[n][j] + sum_arr[i][j]
            
            num = num1 * num2 * num3
            max_num = max(max_num, num)
            
    # 4.
    for i in range(1, n):
        for j in range(1, m):
            num1 = sum_arr[n][j] - sum_arr[0][0]
            num2 = sum_arr[i][m] - sum_arr[i][j]
            num3 = sum_arr[n][m] - sum_arr[i][m] - sum_arr[n][j] + sum_arr[i][j]
            
            num = num1 * num2 * num3
            max_num = max(max_num, num)
            
    # 5.
    for i in range(1, m-1):
        for j in range(i+1, m):
            num1 = sum_arr[n][i] - sum_arr[n][0]
            num2 = sum_arr[n][j] - sum_arr[n][i]
            num3 = sum_arr[n][m] - sum_arr[n][j]
            
            num = num1 * num2 * num3
            max_num = max(max_num, num)
            
    # 6.
    for i in range(1, n-1):
        for j in range(i+1, n):
            num1 = sum_arr[i][m] - sum_arr[0][m]
            num2 = sum_arr[j][m] - sum_arr[i][m]
            num3 = sum_arr[n][m] - sum_arr[j][m]
            
            num = num1 * num2 * num3
            max_num = max(max_num, num)
            
print(max_num)

백준 1451 직사각형으로 나누기