시간 제한 3초
문제
자신의 몸이 허약하다고 생각한 정택은 강해지기위해 운동을 하기 시작했다. 알고리즘 피트니스 센터의 센터장인 종민의 조언에 따라 “먹는 것 까지 운동이다.” 라는 철칙을 잘 따르고 있다. 전날 무리하게 운동한 여파로 늦잠을 자게되어, 오늘 먹을 단백질 도시락을 챙길 여유가 없었다. 어제 무리하게 운동한 것이 아까운 정택은 사무실 근처에 있는 편의점을 돌며 얻을 수 있는 최대의 단백질을 확보하려고 한다. 또한 같은 단백질 함양을 가진 제품은 동일한 제품이고, 같은 도시락을 여러 번 먹으면 질리기때문에 서로 다른 제품을 통해 단백질을 섭취하고자 한다. 양기가 가득하고자하는 정택은 편의점을 ‘+’ 모양으로 순회하려고 한다.
위와 같이 편의점 정보가 존재한다고 했을 때, 각 칸에 해당하는 숫자는 해당 편의점에서 얻을 수 있는 단백질의 g 수 이다. 첫 번째 그림에서 얻을 수 있는 서로 다른 종류의 단백질 도시락 개수는 4개이며, 얻을 수 있는 단백질 g 수는 7+2+10+9 로 28 이다. 두 번째 그림에서 얻을 수 있는 서로 다른 종류의 단백질 도시락 개수는 5개이며, 얻을 수 있는 단백질 g 수는 1+3+4+9+10 로 27 이다.
순회 경로의 경우 만약 중앙을 기점으로 봤을 때, 상하좌우 경로의 길이를 서로 달리할 수 있다. 이때 경로의 길이 최솟값은 1로 고정한다. 즉, 하나의 편의점만 들를 수 없고, 직선 형태, 'ㄱ', 'ㄴ' 등의 모양으로 순회를 할 수 없다는 것이다. 예를 들면, 다음과 같이 다양하게 존재할 수 있다.
시작 지점에서 출발하여 다시 시작 지점으로 돌아온다고 했을 때, N * N 의 편의점 단백질 도시락 정보에서 가장 많은 종류의 단백질 도시락을 얻을 수 있는 경로를 찾고, 해당 경로에서 얻을 수 있는 단백질 함량의 합을 구해보자.
편의점 정보가 주어졌을 때, 답을 구하는 과정은 다음과 같다. (총 6가지가 존재하는 것은 아니며, 몇 가지 경우는 생략되었다.)
마지막 그림에서 얻어지는 숫자의 합 1+2+3+5+6+7+8 인 32 가 정답이다.
입력
첫 번째 줄에 테스트 케이스의 개수 T(5 ≤ T ≤ 50) 가 주어진다. 각 테스트 케이스의 첫째 줄에 N(3 ≤ N ≤ 20) 이 주어지고, N 개의 줄에 걸쳐 N 개의 숫자가 공백을 통해 구분하여 입력된다. 각각의 입력되는 숫자는 1 부터 100 을 포함한 정수이다.
출력
각 테스트 케이스에 해당하는 결과값을 한 줄에 하나씩 “#t result” 포맷으로 출력한다. (t는 1부터 T까지의 정수이다)
예제 입력
5
4
7 8 6 10
9 2 7 1
6 5 1 3
1 7 5 9
10
7 7 5 8 3 1 5 6 4 4
1 8 4 4 4 6 3 7 9 3
8 8 6 7 3 8 5 4 3 7
3 4 1 6 4 3 5 3 2 7
9 9 1 8 3 9 6 4 2 2
4 5 5 7 4 7 1 8 9 6
1 7 7 8 5 2 6 1 5 2
3 9 6 1 8 2 3 4 5 4
2 1 1 2 9 6 1 4 6 6
9 2 4 6 7 1 4 3 8 6
8
4 7 1 6 8 5 8 7
4 5 6 1 9 1 1 8
7 2 1 4 1 7 1 1
3 8 6 2 5 2 5 1
9 8 8 4 8 7 8 9
1 2 2 4 3 3 9 4
3 9 3 2 2 8 5 9
4 3 4 2 3 4 6 6
6
5 3 9 3 7 5
9 4 9 1 5 4
3 3 7 8 1 6
6 8 7 3 3 3
1 3 9 8 5 6
1 1 3 7 6 3
4
7 7 3 6
1 3 2 1
9 6 1 8
2 2 2 2예제 출력
#1 32
#2 45
#3 45
#4 39
#5 36
댓글 없음:
댓글 쓰기