이동하기

면접 대비

시간 제한1초메모리 제한256 MB

요약

왼쪽 위 방에서 출발해 오른쪽, 아래쪽, 대각선 이동으로 오른쪽 아래 방까지 가며 모을 수 있는 사탕의 최댓값을 구합니다.

난이도: 쉬움10점 중 3점
유형: 동적 계획법, 행렬
정답자: 아직 제출이 없습니다

문제

준규는 $N \times M$ 크기의 미로에 갇혀 있다. 미로는 $1 \times 1$ 크기의 방으로 나뉘어 있고, 각 방에는 사탕이 놓여 있다. 가장 왼쪽 위 방이 $(1, 1)$ 이고, 가장 오른쪽 아래 방이 $(N, M)$ 이다.

준규는 지금 $(1, 1)$ 에 있고 $(N, M)$ 까지 가려고 한다. $(r, c)$ 에 있으면 $(r+1, c)$ , $(r, c+1)$ , $(r+1, c+1)$ 중 한 곳으로 이동할 수 있고, 방을 방문할 때마다 그 방에 놓인 사탕을 모두 가져갈 수 있다. 미로 밖으로 나갈 수는 없다.

준규가 $(N, M)$ 까지 이동하면서 가져올 수 있는 사탕 개수의 최댓값을 구하시오. 출발하는 방 $(1, 1)$ 의 사탕도 가져간다.

입력

첫째 줄에 미로의 크기 $N$ 과 $M$ 이 주어진다. ( $1 \le N, M \le 1000$ )

둘째 줄부터 $N$ 개 줄에 각각 $M$ 개의 수가 주어진다. $r$ 번째 줄의 $c$ 번째 수는 방 $(r, c)$ 에 놓인 사탕의 개수이며, 0 이상 100 이하이다.

출력

첫째 줄에 준규가 $(N, M)$ 까지 이동하면서 가져올 수 있는 사탕 개수의 최댓값을 출력한다.

예제4

예제 1
입력
```
3 4
1 2 3 4
0 0 0 5
9 8 7 6
```
예상 출력
```
31
```
예제 2
입력
```
3 3
1 0 0
0 1 0
0 0 1
```
예상 출력
```
3
```
예제 3
입력
```
4 3
1 2 3
6 5 4
7 8 9
12 11 10
```
예상 출력
```
47
```
예제 4
입력
```
1 1
0
```
예상 출력
```
0
```