양의 정수들로 구성된 N*N 크기의 격자 행렬이 주어집니다. 당신은 이 행렬의 좌상단(1행 1열)에서 출발하여 우하단(N행 N열)까지 이동하려고 합니다.

이동할 때는 다음과 같은 제약 조건을 지켜야 합니다.

• 오직 오른쪽 또는 아래쪽으로만 이동할 수 있습니다.

• 왼쪽, 위쪽, 혹은 대각선 방향으로의 이동은 절대 허용되지 않습니다.

좌상단에서 우하단까지 이동하는 경로 상의 칸에 적힌 수들을 모두 더했을 때, 그 합의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 행렬의 크기 N이 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 행렬의 원소들이 각 행별로 N개씩 공백을 사이에 두고 주어진다.

출력

좌상단에서 우하단까지 제약 조건을 만족하며 이동할 때, 거쳐간 칸에 있는 수들의 합의 최댓값을 첫째 줄에 출력한다.

제한 사항

• 1 ≤ N ≤ 500

• 행렬의 각 원소는 1 이상 1,000 이하의 자연수이다.

First line \(N\) (\(1 \le N \le 500\)); then \(N\) rows of \(N\) integers, each in \([1, 1000]\).

Print the maximum path sum.

riseoj 작성

출처 Online Judge > GoldOJ