27508번 - 던전 서브태스크언어 제한함수 구현

철수와 영희는 게임을 하는 도중 던전을 통과하게 되었다. 던전은 가로 $N$칸, 세로 $N$칸인 격자 모양이다. 격자의 행들은 위에서부터 $0$부터 $N - 1$까지 번호가 붙어져 있으며, 격자의 열들은 왼쪽부터 $0$부터 $N - 1$까지 번호가 붙어져 있다. $i$번 행, $j$번 열에 위치한 칸을 칸 $(i, j)$라고 부른다.

던전을 통과하는 규칙은 아래와 같다.

• 철수는 던전의 제일 왼쪽 위 칸에서 출발하여 제일 오른쪽 아래 칸으로 이동한다. 이동할 때, 철수는 현재 위치한 칸에서 오른쪽 혹은 아래로 바로 인접한 칸으로만 이동이 가능하다.
• 영희는 던전의 제일 오른쪽 위 칸에서 출발하여 제일 왼쪽 아래 칸으로 이동한다. 이동할 때, 영희는 현재 위치한 칸에서 왼쪽 혹은 아래로 바로 인접한 칸으로만 이동이 가능하다.

던전의 각 칸에는 아이템이 하나씩 있다. 각 아이템의 가치는 양의 정수, $0$, 혹은 음의 정수이며, 칸 $(i, j)$ 에 있는 아이템의 가치는 $V[i][j]$이다. 철수와 영희는 모든 칸에 있는 아이템의 가치를 이미 다 알고 있다. 던전을 통과하고 나면 철수와 영희가 지나간 모든 칸의 아이템들을 다 모으게 된다. 두 사람이 모두 지나간 칸에서도 아이템은 하나만 모으게 된다는 것에 주의하라.

철수와 영희가 모으는 아이템 가치 합의 가능한 최댓값을 구하는 프로그램을 작성하라.

여러분은 아래 함수를 구현해야 한다.

int max_item_sum(vector<vector<int> > V)

• $V$: 크기가 $N \times N$인 $2$차원 정수 배열. 모든 $i$, $j$ ($0 ≤ i, j ≤ N - 1$)에 대해, $V[i][j]$는 던전의 칸 $(i, j)$에 있는 아이템의 가치이다.
• 이 함수는 철수와 영희가 모을 수 있는 아이템 가치 합의 가능한 최댓값을 반환해야 한다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

• $2 ≤ N ≤ 1\,000$
• 모든 $i$, $j$에 대해 $-100\,000 ≤ V[i][j] ≤ 100\,000$ ($0 ≤ i, j ≤ N - 1$)

$N = 5$, $V = [[−1, −1, −1, −1, −1], [−1, −1, 1, −1, −1], [−1, −1, −1, −1, −1], [−1, −1, 1, −1, −1], [−1, −1, −1, −1, −1]]$인 경우를 생각해 보자.

그레이더는 다음과 같이 함수를 호출한다.

max_item_sum([[-1, -1, -1, -1, -1], [-1, -1, 1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, 1, -1, -1], [-1, -1, -1, -1, -1]])

아래 그림은 이 경우의 던전을 표현한 것이다. 각 칸에 기록된 값은 그 칸의 아이템의 가치이다.

아래 그림의 왼쪽의 파란 색 칸들은 철수가 지나간 칸 들, 오른쪽의 노란 색 칸들은 영희가 지나간 칸들을 표시한다. 철수만 지나간 칸들에서 아이템들의 가치 합은 $-4$, 영희만 지나간 칸들에서 아이템들의 가치 합도 $-4$이며, 두 명이 모두 지나간 칸들에서 아이템들이 가치 합은 $-1$이다. 따라서, 아이템들의 총 가치 합은 $-9$ 이며, 이 경우가 가치의 합이 최대인 경우이다.

함수는 $-9$를 반환해야 한다.

$N = 5$, $V = [[1, 2, 3, 4, 5], [2, 3, 4, 5, 1], [3, 4, 5, 1, 2], [4, 5, 1, 2, 3], [5, 1, 2, 3, 4]]$인 경우를 생각해 보자. 그레이더는 다음과 같이 함수를 호출한다.

max_item_sum([[1, 2, 3, 4, 5], [2, 3, 4, 5, 1], [3, 4, 5, 1, 2], [4, 5, 1, 2, 3], [5, 1, 2, 3, 4]])

함수는 $60$을 반환해야 한다.

$N = 5$, $V = [[1, 1, −1, −1, 1], [−1, 1, −1, 1, 1], [1, 1, 1, 1, −1], [1, −1, −1, 1, −1], [1, −1, −1, 1, 1]]$인 경우를 생각해 보자.

그레이더는 다음과 같이 함수를 호출한다.

max_item_sum([[1, 1, -1, -1, 1], [-1, 1, -1, 1, 1], [1, 1, 1, 1, -1], [1, -1, -1, 1, -1], [1, -1, -1, 1, 1]])

함수는 $15$를 반환해야 한다.

Sample grader는 아래와 같은 형식으로 입력을 받는다.

• Line $1$: $N$
• Line $2 + i$ ($0 ≤ i ≤ N - 1$): $V[i][0]$ $V[i][1]$ $\cdots$ $V[i][N - 1]$

Sample grader는 다음을 출력한다.

• Line $1$: 함수 max_item_sum가 반환한 값

Sample grader는 실제 채점에서 사용하는 그레이더와 다를 수 있음에 유의하라.

• dungeon_public.zip