Best Path On A Diamond

문제 정보

문제

6 
   1 2 
  6 7 4
 9 4 1 7
6 7 5 9 4
 4 4 3 2 
  1 2 3 
   6 1
    7

위 그림과 같이 자연수들이 다이아몬드 형태대로 배치되어 있다. 이 때, 각 가로줄에서 한 개씩의 숫자를 골라 맨 위에서 맨 아래칸으로 내려오는 경로를 구성하고 싶다. 경로에서 앞뒤에 위치한 숫자들은 서로 인접해 있어야 한다: 예를 들어, 위 그림에서 세 번째 줄의 7 은 그 아랫 줄의 4 또는 1 과만 이어질 수 있다.

이와 같은 경로 중, 포함된 숫자의 합이 가장 큰 경로를 찾고 해당 숫자의 합을 계산하시오.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 100) 가 주어진다. 각 테스트 케이스의 첫 줄에는 다이아몬드 가운데 줄의 가로 길이 N (1 <= N <= 100) 이 주어진다. 그 후 2*N-1 줄에, 맨 윗 줄부터, 다이아몬드의 각 가로줄에 속한 숫자가 왼쪽부터 순서대로 주어진다. 각 수는 100 이하의 자연수라고 가정해도 좋다.

출력

각 테스트 케이스마다 한 줄에 숫자들의 합이 가장 큰 경로에 대해 해당 합을 출력한다.

예제 입력

2
5
6
1 2
6 7 4
9 4 1 7
6 7 5 9 4
4 4 3 2
1 2 3
6 1
7
5
39
43 16
74 94 24
25 76 98 62
79 58 71 67 98
43 55 27 44
10 96 56
73 31
95

예제 출력

48
664

노트

4개의 댓글이 있습니다.