7152 : 행렬 경로 합 최대
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N×M 크기의 행렬이 주어지고, 각 칸에 양의 정수가 적혀있습니다. (1,1)에서 출발하여 (N,M)까지 오른쪽과 아래로만 이동할 때, 거쳐간 칸에 적힌 수들의 합 중 최댓값을 출력하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 행렬의 크기 N, M이 주어집니다. (1 ≤ N, M ≤ 20)
둘째 줄부터 N개의 줄에 각각 M개의 정수가 공백으로 구분되어 주어집니다. (각 정수 ≤ 100)
둘째 줄부터 N개의 줄에 각각 M개의 정수가 공백으로 구분되어 주어집니다. (각 정수 ≤ 100)
출력 설명
(1,1)에서 (N,M)까지 경로의 합의 최댓값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
1 2 3
4 5 6
7 8 9
출력 예시
COPY
복사되었습니다!
복사되었습니다!
29도움
경로 (1,1) → (2,1) → (3,1) → (3,2) → (3,3) (1 → 4 → 7 → 8 → 9)을 따라 이동할 때 합이 1 + 4 + 7 + 8 + 9 = 29로 최댓값입니다.