[백준 알고리즘] 1451번 Python 풀이

완전탐색 - 1476, 1107, 1451, 9095, 10819, 10971, 1697, 1963, 9019, 1525, 2251, 2186, 3108, 5014, 1759, 2580, 1987, 6603, 1182, 2003, 1806, 1644, 1261, 1208, 7453, 2632, 2143

출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]

알고리즘 문제풀이(PS) 시작하기

 

 

 

백준 알고리즘 1451번

 

 

처음 문제를 접근했을 때, '직사각형의 합의 곱을 최대로'에 주목해 삽질을 좀 하다가 영 답이 나오지 않았는데, 저지 운영자인 백준님이 직접 올려주신 풀이를 발견했다.

www.slideshare.net/Baekjoon/baekjoon-online-judge-1451 

풀이를 간단히 보면 직사각형을 3개의 작은 직사각형으로 나누는 방법은 총 6가지인데, 각각 경우의 수를 모두 탐색해 합의 곱을 비교해보고, 그 중 최댓값을 출력하는 방식이다.

 

1번부터 6번까지 각 상황을 코드로 직접 풀어 냈다.
ㄱ, ㄴ, ㄷ를 나누는 선은 i, j를 사용해 반복적으로 그 범위가 바뀌도록 지정했다.
주의할 점은, i, j 모두 인덱스이기 때문에 선 위에 수가 위치하게 되는데,
각 직사각형 ㄱ, ㄴ, ㄷ을 계산할 때 중복되지 않도록 유의해야 한다.

n, m = map(int, input().split())

# 입력받은 전체 직사각형을 저장하기 위한 리스트(편리한 인덱싱을 위해 행 삽입)
rectangle_input = [[0 for _ in range(m + 1)]]


for _ in range(n):
    # 라인별로 읽고 rectangle_input에 저장(편리한 인덱싱을 위해 [0] 삽입)
    line_input = [0] + list(map(int, list(input())))
    rectangle_input.append(line_input)


# 답은 최댓값을 출력해야 하므로, 0으로 시작
ans = 0

# 합을 저장할 리스트
s = [[0 for _ in range(m+1)] for _ in range(n+1)]

# 리스트 s는 입력받은 직사각형의 1,1부터 영역 내 모든 수의 합을 저장
for row in range(1, n + 1):
    for col in range(1, m + 1):
        s[row][col] = s[row - 1][col] + s[row][col - 1] - s[row - 1][col - 1] + rectangle_input[row][col]


def sum_cal(x1, y1, x2, y2):
    return s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]


# 첫 번째 경우: 전체 직사각형을 세로로만 분할한 경우
for i in range(1, m-1):
    for j in range(i+1, m):
        r1 = sum_cal(1, 1, n, i)
        r2 = sum_cal(1, i+1, n, j)
        r3 = sum_cal(1, j+1, n, m)
        if ans < r1 * r2 * r3:
            ans = r1 * r2 * r3


# 두 번째 경우: 전체 직사각형을 가로로만 분할한 경우
for i in range(1, n-1):
    for j in range(i+1, n):
        r1 = sum_cal(1, 1, i, m)
        r2 = sum_cal(i+1, 1, j, m)
        r3 = sum_cal(j+1, 1, n, m)
        if ans < r1 * r2 * r3:
            ans = r1 * r2 * r3

# 세 번째 경우: 전체 세로 분할 후 우측 가로 분할한 경우
for i in range(1, m):
    for j in range(1, n):
        r1 = sum_cal(1, 1, n, i)
        r2 = sum_cal(1, i+1, j, m)
        r3 = sum_cal(j+1, i+1, n, m)
        if ans < r1 * r2 * r3:
            ans = r1 * r2 * r3

# 네 번째 경우: 전체 세로 분할 후 좌측 가로 분할한 경우
for i in range(1, n):
    for j in range(1, m):
        r1 = sum_cal(1, 1, i, j)
        r2 = sum_cal(i+1, 1, n, j)
        r3 = sum_cal(1, j+1, n, m)
        if ans < r1 * r2 * r3:
            ans = r1 * r2 * r3

# 다섯번 째 경우: 전체 가로 분할 후 하단 세로 분할한 경우
for i in range(1, n):
    for j in range(1, m):
        r1 = sum_cal(1, 1, i, m)
        r2 = sum_cal(i+1, 1, n, j)
        r3 = sum_cal(i+1, j+1, n, m)
        if ans < r1 * r2 * r3:
            ans = r1 * r2 * r3

# 여섯번 째 경우: 전체 가로 분할 후 상단 세로 분할한 경우
for i in range(1, n):
    for j in range(1, m):
        r1 = sum_cal(1, 1, i, j)
        r2 = sum_cal(1, j+1, i, m)
        r3 = sum_cal(i+1, 1, n, m)
        if ans < r1 * r2 * r3:
            ans = r1 * r2 * r3

print(ans)