BOJ 1451 직사각형으로 나누기

https://www.acmicpc.net/problem/1451
시간 2초, 메모리 128MB
input :

• N M(1 <= N M <= 100)
• 직사각형엔 적어도 3개의 수가 있다. 또, 직사각형에 들어가는 수는 한 자리의 숫자

output :

• 세 개의 작은 직사각형의 합의 곱의 최댓값을 출력

---

직사각형을 나누는 경우가 6가지가 존재한다.

그리고 이 직사각형의 안의 수들의 합을 구해야 하기 때문에. 매번 테이블에 반복문을 돌려서 모든 합을 구하든지 아니면 다른 리스트를 가져와서 미리 합을 구해놓아야 한다.

합의 경우. target = x, y
(1, 1) 에서 (x - 1, y) 값을 더한 값이 s[x - 1][y]에 저장되어 있고.
(1, 1) 에서 (x, y - 1) 까지의 값이 s[x][y - 1]에 저장되어 있고..
(1, 1) 에서 (x - 1, y - 1) 까지의 값은 2번 더해 져서 1번 빼주고,
data[x, y]의 값을 더 해 준다.

https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1451
사각형을 나누는 모양새를 볼 때에. 한 지점을 i, j 로 만들어 놓고 3가지 모양의 직사각형의 합을 구하도록 한다.

import sys

n, m = map(int, sys.stdin.readline().split())
data = [[0] * (m + 1) for i in range(n + 1)]
s = [[0] * (m + 1) for i in range(n + 1)]
for i in range(1, n + 1):
    a = list(map(int, sys.stdin.readline().strip()))
    for j in range(1, len(a) + 1):
        data[i][j] = a[j - 1]

for i in range(1, n + 1):
    for j in range(1, m + 1):
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + data[i][j]


def add(x, y, nx, ny):
    return s[nx][ny] - s[nx][y - 1] - s[x - 1][ny] + s[x - 1][y - 1]


ans = 0
# 직사각형의 모양이 세로로 3가지 일 때.
# 세로 길이는 n으로 고정이고. 가로길이를 3등분 해야 하기 때문에
# 1 ~ i, i + 1 ~ j, j + 1 ~ m
for i in range(1, m - 1):
    for j in range(i + 1, m):
        r1 = add(1, 1, n, i)
        r2 = add(1, i + 1, n, j)
        r3 = add(1, j + 1, n, m)
        ans = max(ans, r1 * r2 * r3)

# 직사각형의 모양이 가로로 3가지 일 때.
# 가로 길이는 m으로 고정이고. 세로길이를 3등분 해야 하기 때문에
# 1 ~ i, i + 1 ~ j, j + 1 ~ n
for i in range(1, n - 1):
    for j in range(i + 1, n):
        r1 = add(1, 1, i, m)
        r2 = add(i + 1, 1, j, m)
        r3 = add(j + 1, 1, n, m)
        ans = max(ans, r1 * r2 * r3)

for i in range(1, n):
    for j in range(1, m):
        # 세로로 n을 가지는 모양
        r1 = add(1, 1, n, j)
        # 가로 모양 중 위에 꺼.
        # 1, j + 1 에 위치 위의 세로 모양이 n, j 까지의 넓이를 가지기 때문.
        r2 = add(1, j + 1, i, m)
        r3 = add(i + 1, j + 1, n, m)
        ans = max(ans, r1 * r2 * r3)

        r1 = add(1, 1, i, j)
        r2 = add(i + 1, 1, n, j)
        r3 = add(1, j + 1, n, m)
        ans = max(ans, r1 * r2 * r3)

        r1 = add(1, 1, i, m)
        r2 = add(i + 1, 1, n, j)
        r3 = add(i + 1, j + 1, n, m)
        ans = max(ans, r1 * r2 * r3)

        r1 = add(1, 1, i, j)
        r2 = add(1, j + 1, i, m)
        r3 = add(i + 1, 1, n, m)
        ans = max(ans, r1 * r2 * r3)
print(ans)