[Python/BOJ] 25708. 만남의 광장

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

25708번: 만남의 광장

문제

인하대학교의 마스코트인 인덕이가 사는 인경호는 인하대학교 학생이 아니여도 주변에 거주하는 사람들이 산책로로 이용할 수 있다. 인하대학교는 인경호에서 산책하는 사람들이 많은 것을 알고 이들을 위해 인경호 근처에 적당한 녹지를 골라 만남의 광장을 만들기로 하였다.

만남의 광장은 위 그림과 같이 N × M 크기의 녹지에 각각 다른 행을 골라 가로 방향으로 2개, 각각 다른 열을 골라 세로 방향으로 2개의 직선으로 뻗은 4개의 길을 놓아 만든다. 녹지의 i행 j열의 칸에는 가치 dij가 정해져있다.

인하대학교는 녹지에 만남의 광장을 만들 때 광장의 아름다움을 최대화하려고 한다. 이때, 광장의 아름다움이란 4개의 길에 둘러싸인 직사각형 꼴 영역에 포함된 녹지인 칸의 개수에 길이 깔린 모든 칸의 가치를 더한 값이다. 광장의 아름다움은 0보다 작을 수 있다.

만남의 광장을 만들기 위해 고른 녹지의 크기와 모든 칸 각각의 가치가 주어질 때, 만남의 광장의 아름다움을 최대화했을 때의 아름다움을 출력하여라.

입력

첫 번째 줄에 만남의 광장을 만들 녹지의 크기 N과 M이 공백으로 구분되어 주어진다.

두 번째 줄부터 N개의 줄에 걸쳐 녹지의 각 칸에 길을 놓을 때 광장의 아름다움에 영향을 끼치는 정도 dij가 M개씩 공백으로 구분되어 주어진다.

출력

주어진 녹지에 만남의 광장을 만들 때 광장의 아름다움의 최댓값을 출력한다.

풀이

Code