최대 코인
면접 대비시간 제한20초메모리 제한1024 MB
이동이 대각선 방향으로만 이루어지므로 경로는 하나의 대각선 위에 머문다. 각 대각선의 동전 합 중 최댓값을 구한다.
문제
Mike에게는 N개의 행과 N개의 열로 이루어진 정사각 행렬이 있다. (i,j)는 i번째 행과 j번째 열에 있는 칸을 나타낸다. 칸 (1,1)은 행렬의 왼쪽 위 모서리이다. 각 칸에는 코인이 몇 개씩 있고, Mike는 그 칸을 방문해야만 코인을 얻는다. Ci,j는 i번째 행과 j번째 열에 있는 칸의 코인 개수이다. Mike는 칸 (i,j)에서 (i+1,j+1) 또는 (i-1,j-1)로 이동할 수 있으며, 이동하려는 칸이 행렬 범위 안에 있고 아직 방문하지 않은 칸이어야 한다. 그는 어느 칸에서든 여정을 시작할 수 있고 어느 시점에서든 멈출 수 있다. Mike는 얻을 수 있는 코인의 개수를 최대화하려고 한다. 그가 얻을 수 있는 최대 코인 개수를 구하시오.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 N이 주어진다. 다음 N개의 줄에는 각각 N개의 정수가 주어진다. i번째 줄의 j번째 정수는 칸 (i,j)의 코인 개수 Ci,j이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 Mike가 얻을 수 있는 최대 코인 개수이다.
제한
- 1 ≤ T ≤ 100.
- 0 ≤ Ci,j ≤ 107.
힌트
샘플 케이스 #1에서 Mike가 (1,1) -> (2,2) -> (3,3) 경로를 따라가면 최대 14개의 코인을 얻을 수 있다.
샘플 케이스 #2에서 Mike가 (2,3) -> (3,4) 경로를 따라가면 최대 9개의 코인을 얻을 수 있다.