실버 III설명
광석을 수집하는 SCV가 \(N \times M\) 격자 지대에서 작업합니다. SCV는 항상 오른쪽 또는 아래쪽으로만 이동할 수 있습니다.
맨 왼쪽 위 \((1, 1)\)에서 출발하여 맨 오른쪽 아래 \((N, M)\)에서 작업을 종료합니다. 이동 경로상의 칸에 광석이 있으면 그 광석을 수집합니다.
격자의 크기와 광석 배치가 주어질 때, \((1,1)\)에서 \((N,M)\)까지 이동하며 수집할 수 있는 최대 광석의 개수를 구하시오.
제약
\(1 \le N \le 200\)
\(1 \le M \le 200\)
입력 형식
첫째 줄에 세로 크기 \(N\)과 가로 크기 \(M\)이 공백을 사이에 두고 주어진다.
둘째 줄부터 \(N\)개의 줄에 각 줄마다 \(M\)개의 숫자가 공백으로 구분되어 주어진다. \(1\)은 광석이 있는 칸, \(0\)은 빈 칸을 의미한다.
출력 형식
첫째 줄에 수집할 수 있는 최대 광석의 개수를 출력한다.
예제 1
입력
5 4
0 1 0 0
0 0 1 0
1 1 0 0
1 0 1 0
1 1 0 0
출력
4
설명
오른쪽/아래로만 이동하여 광석을 최대 \(4\)개 모을 수 있다.
예제 2
입력
1 1
1
출력
1
설명
칸이 하나뿐이며 광석이 있으므로 \(1\).
예제 3
입력
1 1
0
출력
0
설명
유일한 칸이 비어 있으므로 \(0\).
문제 정보
riseoj 작성
출처 Original
태그