연습문제

나무 조경

난이도
Lv. 3
제출
720 명
참가자
528 명
정답률
74.59 %
지원 언어
C
C++
Java
Python
JavaScript
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
C++ 1초 1024MB
JavaScript 3초 1024MB
C 1초 1024MB
Java 1초 1024MB
Python 3초 1024MB

남우는 우후죽순으로 자라 있는 나무들을 잘 정리하여 정원을 가꾸려고 합니다. 정원은 n × n 격자 모양으로 이루어져 있으며, 각 칸에는 하나의 나무가 심어져 있습니다. 상하좌우로 맞닿아 있는 경우를 인접한 경우라고 했을 때, 남우는 최대 4번 인접해 있는 두 나무를 묶는 것을 진행하려고 합니다. 이때 묶은 나무끼리는 서로 겹쳐서는 안 되며, 두 나무가 묶였을 때 얻을 수 있는 아름다움은 두 나무의 키의 합과 동일하다고 합니다. 이러한 상황에서 묶인 쌍의 아름다움의 합을 최대로 만들어보려고 합니다.


예를 들어 n = 4 일 때 다음과 같이 정원 정보가 주어진 경우를 생각해보겠습니다. 각 격자 칸에 적혀있는 숫자는 각 칸에 있는 나무들의 키를 의미합니다.





이때 다음과 같이 나무들을 묶게 되면 서로 묶은 쌍끼리 겹치지 않되 얻을 수 있는 아름다움의 합이 25(=7+6+7+5)로 최대가 됩니다.





초기 격자의 상태가 주어졌을 때 최대 4개의 쌍을 겹치지 않게 잘 골라 얻을 수 있는 아름다움의 총 합을 최대로 하는 프로그램을 작성해보세요.



본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.

제약조건

  • 2 ≤ n ≤ 4
  • 1 ≤ 나무의 키 ≤ 10

입력형식

첫 번째 줄에는 격자의 크기를 나타내는 n이 주어집니다.
두 번째 줄부터는 n개의 줄에 걸쳐 각 행에 해당하는 나무의 키 정보 n개가 공백을 사이에 두고 주어집니다.

출력형식

첫 번째 줄에 최대 4개의 쌍을 서로 겹치지 않게 묶어 얻을 수 있는 최대 아름다움의 합을 출력합니다. 꼭 4쌍을 전부 골라도 되지 않음에 유의합니다.

입력예제1

4
2 1 3 3
5 1 2 1
2 1 2 3
5 1 1 1
출력예제1

25

입력예제2

2
1 2
3 4
출력예제2

10

입력예제3

3
7 4 5
7 3 5
4 6 6
출력예제3

44

목록