조약돌

시간 제한1초메모리 제한128 MB

요약
N×N 보드에서 대각선으로도 인접하지 않게 돌을 놓아 덮은 칸 값의 합을 최대로 만든다.
난이도

보통10점 중 6점

유형
동적 계획법, 비트 연산, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

N×NN \times N 크기의 게임판에 조약돌을 원하는 만큼 놓을 수 있습니다. 여기서 3≤N≤153 \le N \le 15 입니다. 각 칸에는 1010 이상 9999 이하의 양의 점수가 하나씩 적혀 있습니다. 예를 들어 6×66 \times 6 게임판은 다음과 같이 생겼을 수 있습니다.

337426557954
675691724432
446422912961
613276505032
816556389636
387850929075

다음 두 규칙을 지키며 조약돌을 놓습니다.

  • 한 칸에는 조약돌을 최대 한 개만 놓을 수 있습니다.
  • 서로 인접한 두 칸에 동시에 조약돌을 놓을 수 없습니다. 두 칸은 가로, 세로, 또는 대각선으로 맞닿아 있으면 인접한 것으로 봅니다.

게임판은 반대쪽 끝과 이어지지 않으므로, 같은 행이나 열의 양쪽 끝 칸, 그리고 서로 멀리 떨어진 두 모서리 칸은 인접하지 않습니다.

점수는 조약돌이 놓인 모든 칸의 점수를 합한 값입니다. 이 점수를 최대로 만드세요.

입력에는 여러 개의 게임판이 들어올 수 있으며, 각 게임판마다 얻을 수 있는 최대 점수를 구합니다.

입력

각 게임판은 NN개의 줄로 이루어지며, 한 줄에는 공백으로 구분된 NN개의 점수(칸마다 하나씩)가 들어 있습니다. 게임판 사이는 빈 줄로 구분됩니다. 입력이 끝날 때까지 게임판을 계속 읽습니다.

출력

각 게임판마다 규칙을 지키며 얻을 수 있는 최대 점수를 정수 하나로 한 줄에 출력합니다.

예제1

  1. 예제 1

    입력
    71 24 95 56 54
85 50 74 94 28
92 96 23 71 10
23 61 31 30 46
64 33 32 95 89

78 78 11 55 20 11
98 54 81 43 39 97
12 15 79 99 58 10
13 79 83 65 34 17
85 59 61 12 58 97
40 63 97 85 66 90

33 49 78 79 30 16 34 88 54 39 26
80 21 32 71 89 63 39 52 90 14 89
49 66 33 19 45 61 31 29 84 98 58
36 53 35 33 88 90 19 23 76 23 76
77 27 25 42 70 36 35 91 17 79 43
33 85 33 59 47 46 63 75 98 96 55
75 88 10 57 85 71 34 10 59 84 45
29 34 43 46 75 28 47 63 48 16 19
62 57 91 85 89 70 80 30 19 38 14
61 35 36 20 38 18 89 64 63 88 83
45 46 89 53 83 59 48 45 87 98 21

15 95 24 35 79 35 55 66 91 95 86 87
94 15 84 42 88 83 64 50 22 99 13 32
85 12 43 39 41 23 35 97 54 98 18 85
84 61 77 96 49 38 75 95 16 71 22 14
18 72 97 94 43 18 59 78 33 80 68 59
26 94 78 87 78 92 59 83 26 88 91 91
34 84 53 98 83 49 60 11 55 17 51 75
29 80 14 79 15 18 94 39 69 24 93 41
66 64 88 82 21 56 16 41 57 74 51 79
49 15 59 21 37 27 78 41 38 82 19 62
54 91 47 29 38 67 52 92 81 99 11 27
31 62 32 97 42 93 43 79 88 44 54 48
    예상 출력
    572
683
2096
2755