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

출처 : 1451번: 직사각형으로 나누기 (acmicpc.net)

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

직사각형으로 나누기 성공분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초

128 MB

2250

804

613

37.039%

문제

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

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

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

입력

첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 직사각형엔 적어도 3개의 수가 있다. 또, 직사각형에 들어가는 수는 한 자리의 숫자이다.

출력

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

 

---

[ 문제 설명 ]

 

이 문제는 합의 곱을 구하는 문제이다.

 

문제에 대한 설명은 그림으로 하겠다.

 

그림 1 - 직사각형 나누기 아이디어

그림 2 - 직사각형 나누기 아이디어

그림 3 - 직사각형 나누기 아이디어

 

위 그림에서 실제로 값은 1 이 나오지 않습니다 실제로는 (0,0) ~ (3,0) , (0,1) ~ (0,3) = 0 값이지만 이해를 직관적으로 쉽게 하기 위하여 저렇게 그렸고 사실 저도 표는 (1,1) ~ (3,2) 좌표의 값이 더 정확하고 맞습니다.

제 설명이 이해가 된다면 다 이해하셨다고 볼 수 있고 이해가 되지 않는다면 제가 설명을 잘못함 + 다른 블로그나 다른 고수분의 참고 또는 이용하셔야 할 거 같습니다.

그림4 - 직사각형 나누기 아이디어

---

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

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


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

print(retangle)

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

# 합을 저장할 리스트
sum = [[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):
        sum[row][col] = sum[row - 1][col] + sum[row][col - 1] - sum[row - 1][col - 1] + retangle[row][col]

print(sum)


def sumCalculate(x1, y1, x2, y2):
    return sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]


# 첫 번째 경우: 세로로만 분할한 경우
for i in range(1, m-1):
    for j in range(i+1, m):
        r1 = sumCalculate(1, 1, n, i)  # print(n, i, r1)
        r2 = sumCalculate(1, i + 1, n, j)  # print(n, j, r2)
        r3 = sumCalculate(1, j + 1, n, m)
        if res < r1 * r2 * r3:  # 경우의 수는 곱으로 계산함, 최대값 계산
            res = r1 * r2 * r3


# 두 번째 경우: 가로로만 분할한 경우
for i in range(1, n-1):
    for j in range(i+1, n):
        r1 = sumCalculate(1, 1, i, m)
        r2 = sumCalculate(i + 1, 1, j, m)
        r3 = sumCalculate(j + 1, 1, n, m)
        if res < r1 * r2 * r3:  # 경우의 수는 곱으로 계산함, 최대값 계산
            res = r1 * r2 * r3

# 세 번째 경우: 전체 세로 분할 후 우측 가로 분할한 경우
for i in range(1, m):
    for j in range(1, n):
        r1 = sumCalculate(1, 1, n, i)
        r2 = sumCalculate(1, i + 1, j, m)
        r3 = sumCalculate(j + 1, i + 1, n, m)
        if res < r1 * r2 * r3:  # 경우의 수는 곱으로 계산함, 최대값 계산
            res = r1 * r2 * r3

# 네 번째 경우: 전체 세로 분할 후 좌측 가로 분할한 경우
for i in range(1, n):
    for j in range(1, m):
        r1 = sumCalculate(1, 1, i, j)
        r2 = sumCalculate(i + 1, 1, n, j)
        r3 = sumCalculate(1, j + 1, n, m)
        if res < r1 * r2 * r3:  # 경우의 수는 곱으로 계산함, 최대값 계산
            res = r1 * r2 * r3

# 다섯번 째 경우: 전체 가로 분할 후 하단 세로 분할한 경우
for i in range(1, n):
    for j in range(1, m):
        r1 = sumCalculate(1, 1, i, m)
        r2 = sumCalculate(i + 1, 1, n, j)
        r3 = sumCalculate(i + 1, j + 1, n, m)
        if res < r1 * r2 * r3:  # 경우의 수는 곱으로 계산함, 최대값 계산
            res = r1 * r2 * r3

# 여섯번 째 경우: 전체 가로 분할 후 상단 세로 분할한 경우
for i in range(1, n):
    for j in range(1, m):
        r1 = sumCalculate(1, 1, i, j)
        r2 = sumCalculate(1, j + 1, i, m)
        r3 = sumCalculate(i + 1, 1, n, m)
        if res < r1 * r2 * r3:  # 경우의 수는 곱으로 계산함, 최대값 계산
            res = r1 * r2 * r3

print(res)

---

후기

 

확실히 한 번 더 복습하니

내가 이해했다고 생각했던 부분이

사실은 이해하지 못했다는 사실을

복습을 할 때마다 느끼게 됩니다.