BOJ 1451번: 직사각형으로 나누기

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

1451번: 직사각형으로 나누기

1. (0,0)을 왼쪽 위 꼭짓점으로 하고 (i,j)를 오른쪽 아래 꼭짓점으로 하는 직사각형의 누적합을 dp[i][j]에 저장

dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1]

2. (0,0)을 포함한 작은 사각형이 (0~N-2, 0~M-2) 인 경우

3. (0,0)을 포함한 작은 사각형이 dp[i][M-1]인 경우

4. (0,0)을 포함한 작은 사각형이 dp[N-1][i]인 경우

이렇게 세 가지 경우를 나눠서 가능한 경우를 모두 따져보면서 ans의 최댓값을 갱신했다.

 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(list(map(int, list(input().rstrip()))))
    
dp = [[0]*M for _ in range(N)]
dp[0][0] = arr[0][0]

for i in range(1, N):
    dp[i][0] = dp[i-1][0] + arr[i][0]
    
for i in range(1, M):
    dp[0][i] = dp[0][i-1] + arr[0][i]

for i in range(1, N):
    for j in range(1, M):
        dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1]

ans = 0
for i in range(N-1):
    for j in range(M-1):
        a = dp[i][j]
        b = dp[i][M-1] - a
        c = dp[N-1][M-1] - a - b
        tmp = a * b * c
        ans = max(ans, tmp)
        b = dp[N-1][j] - a
        c = dp[N-1][M-1] - a - b
        tmp = a * b * c
        ans = max(ans, tmp)
   
for i in range(N):
    a = dp[i][M-1]
    for j in range(i+1, N):
        b = dp[j][M-1] - a
        c = dp[N-1][M-1] - a - b
        tmp = a * b * c
        ans = max(ans, tmp)
    for j in range(M-1):
        b = dp[N-1][j] - dp[i][j]
        c = dp[N-1][M-1] - a - b
        tmp = a * b * c
        ans = max(ans, tmp)

for i in range(M):
    a = dp[N-1][i]
    for j in range(i+1, M):
        b = dp[N-1][j] - a
        c = dp[N-1][M-1] - a - b
        tmp = a * b * c
        ans = max(ans, tmp)
    for j in range(N-1):
        b = dp[j][M-1] - dp[j][i]
        c = dp[N-1][M-1] - a - b
        tmp = a * b * c
        ans = max(ans, tmp)
        
print(ans)