(11048)(DP) 백준 이동하기

https://www.acmicpc.net/problem/11048

풀이

---

NxM의 배열을 받고 (1,1)부터 출발해서 (N,M)에 도착했을때 최대가 될 수 있게 사탕을 챙겨야한다.

이동할 수 있는 방법은     →    /    ↓    /    ↘︎    이렇게 세가지 방법이 있다. 하지만 여기서  사탕은 0보다 같거나 크기 때문에   ↘︎ 으로 갈때 ↓ 와 → or → 와 ↓ 조합으로 이동해도

적어도 손해는 없기 때문에 대각선 이동은 고려하지 않기로한다. 

(i,j) 까지 왔을때  최대값을 구하기 위해서는 (1,1)에서부터 끊임없이 비교를 하며 최대값을 채택해 (i,j)까지 와야한다.

예를 들어 (3,3)좌표에서 최대값을 가지고 싶을때  3,4번 화살표와 같이

(2,3)에서 와야하는지 (3,2)에서 와야하는지 비교가 필요하다.

즉, i 와 j 가 1 이 아닌 경우

---

arr[i][j] += max(arr[i][j-1], arr[i-1][j]); 와 같은 식이 성립한다.

그러면 나머지 두가지 경우가 남는다.

1. j == 1 인 경우

---

위 그림의 1번 화살표와 같이 비교할 필요없이 위에서 아래로 누적해주며 내려오면 된다.

if(j == 1) arr[i][j] += arr[i-1][j]; 

2. i == 1 인 경우

---

그림의 2번 화살표와 같이 오른쪽으로 누적해주기만 하면 되므로

if(i == 1) arr[i][j] += arr[i][j-1]; 과 같은 식이 성립한다. 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define max(a,b) a>b ? a:b
 
int main() {
    int N, M;
    int arr[1001][1001] = { 0 };
 
 
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (i == 1) arr[i][j] += arr[i][j - 1];
            else if (j == 1) arr[i][j] += arr[i - 1][j];
            else arr[i][j] += max(arr[i][j - 1], arr[i - 1][j]);
        }
    }
    printf("%d\n", arr[N][M]);
    
    return 0;
 
}