광석 수집
실버 III의견: 0
광석을 수집하는 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\)은 빈 칸을 의미한다.
첫째 줄에 수집할 수 있는 최대 광석의 개수를 출력한다.
5 4
0 1 0 0
0 0 1 0
1 1 0 0
1 0 1 0
1 1 0 0
4
오른쪽/아래로만 이동하여 광석을 최대 \(4\)개 모을 수 있다.
1 1
1
1
칸이 하나뿐이며 광석이 있으므로 \(1\).
1 1
0
0
유일한 칸이 비어 있으므로 \(0\).
riseoj 작성
출처 Original
평가 및 의견
광석 수집
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
광석 수집