문제 링크
https://www.acmicpc.net/problem/1451
🕒 Python 풀이시간: 40분
n,m=map(int,input().split())
board=[list(map(int,list(input()))) for _ in range(n)]
prefixSum=[[0]*m for _ in range(n)]
for i in range(n):
for j in range(m):
leftUp=0 if i-1<0 or j-1<0 else prefixSum[i-1][j-1]
left=0 if j-1<0 else prefixSum[i][j-1]
up=0 if i-1<0 else prefixSum[i-1][j]
prefixSum[i][j]=board[i][j]+up+left-leftUp
answer=0
for i in range(n):
for j in range(m):
firstX,firstY=i,j
firstSize=prefixSum[firstX][firstY]
if firstX==n-1 and firstY!=m-1:
secondY=m-1
for secondX in range(n-1):
secondSize=prefixSum[secondX][secondY]-prefixSum[secondX][firstY]
thirdSize=prefixSum[n-1][m-1]-prefixSum[firstX][firstY]-prefixSum[secondX][secondY]+prefixSum[secondX][firstY]
answer=max(answer,firstSize*secondSize*thirdSize)
secondX=n-1
for secondY in range(m-1):
secondSize=prefixSum[secondX][secondY]-prefixSum[secondX][firstY]
thirdSize=prefixSum[n-1][m-1]-prefixSum[secondX][secondY]
answer=max(answer,firstSize*secondSize*thirdSize)
elif firstY==m-1 and firstX!=n-1:
secondX=n-1
for secondY in range(m-1):
secondSize=prefixSum[secondX][secondY]-prefixSum[firstX][secondY]
thirdSize=prefixSum[n-1][m-1]-prefixSum[firstX][firstY]-prefixSum[secondX][secondY]+prefixSum[firstX][secondY]
answer=max(answer,firstSize*secondSize*thirdSize)
secondY=m-1
for secondX in range(n-1):
secondSize=prefixSum[secondX][secondY]-prefixSum[firstX][secondY]
thirdSize=prefixSum[n-1][m-1]-prefixSum[secondX][secondY]
answer=max(answer,firstSize*secondSize*thirdSize)
else:
secondX=n-1
secondY=m-1
thirdX=firstX
thirdY=m-1
secondSize=prefixSum[secondX][secondY]-prefixSum[thirdX][thirdY]
thirdSize=prefixSum[thirdX][thirdY]-prefixSum[firstX][firstY]
answer=max(answer,firstSize*secondSize*thirdSize)
thirdX=n-1
thirdY=m-1
secondX=n-1
secondY=firstY
thirdSize=prefixSum[thirdX][thirdY]-prefixSum[secondX][secondY]
secondSize=prefixSum[secondX][secondY]-prefixSum[firstX][firstY]
answer=max(answer,firstSize*secondSize*thirdSize)
print(answer)직사각형 덮기 문제! 📊🔲
2차원 배열에 각 칸에 숫자가 부여되어 있을 때, 한칸도 빼놓지 않고 겹치지 않게 세 개의 직사각형으로 덮을 때, 해당 직사각형 안에서의 숫자들의 합의 곱, 즉, 직사각형의 합의 곱의 최댓값을 구하는 문제이다.
먼저 특정 영역의 합을 묻고 있기 때문에 누적합이라고 생각할 수 있으며, 각 변의 최대 길이가 50이기 때문에 각 세 점을 찾아나가면서 완전탐색으로 구해도 된다고 생각했다. 케이스는 다음과 같이 나누었다. 먼저 첫번째 점을 찍는 경우는 세가지 이다. 반드시 모든 배열이 한 직사각형 안에 포함되어야 하기 때문에 시작점을 첫번째 직사각형은 반드시 포함한다는 가정하에 case를 나누었다.
i) 기존 배열의 윗쪽 면을 그대로 변으로 가지는 직사각형
ii) 기존 배열의 왼쪽 면을 그대로 변으로 가지는 직사각형
iii) 기존 배열의 한쪽 면을 변으로 가지지 않는 직사각형
이렇게 3가지로 나눈 후에 i), ii)의 경우는 각 두가지로 나누어 생각하였다. 가로 축을 기준으로 분할 하여 차지, 세로 축을 기준으로 분할하여 차지. 이렇게 두 가지로 나누어서 두 번째 점을 찾고 나머지를 세번째가 갖는 식으로 구했다.
마지막 iii)은 둘 중 하나가 끝에 점을 차지 하냐 안하냐의 차이 이기 때문에 이 두가지를 구해 주었다.
최종적인 정답은 누적합을 통해 점만 세개를 나누는 가지수를 모두 찾는다면 쉽게 구할 수 있다. 기존 배열에서의 누적합을 구한 후에 양 사이드와 양 사이드가 겹치는 부분의 누적합을 빼주면 된다.
이렇게 Python으로 백준의 "직사각형으로 나누기" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
