백준 11048 이동하기 C++

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

11048번: 이동하기

---

문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

---

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

---

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

---

#include <iostream>
using namespace std;
//백준 11048 이동하기

int max(int a,int b){
    if(a>b){
        return a;
    }
    else{
        return b;
    }
}
int main(void){
    int dp[1001][1001];
    int arr[1001][1001];
 
    int n,m;
    cin >> n >> m;
    for(int i = 0;i<n;i++){ //배열 입력받고 DP테이블 0으로 초기화
        for(int j = 0;j<m;j++){
            cin >> arr[i][j];  
            dp[i][j] = 0;
        }
    }
 
    dp[0][0] = arr[0][0]; //처음 DP테이블은 배열의 값으로
    for(int i = 1;i<m;i++){ //0번째일때 가능한 경우는 배열값 + 왼쪽 DP테이블 값
        dp[0][i] = dp[0][i-1] + arr[0][i];
    }
 
    for(int i = 1;i<n;i++){ //0번 생략하고 1번쨰부터
        for(int j = 0;j<m;j++){
            if(j == 0){ //j가 0일떄는 하나의 경우(위에서 내려오는 경우)
                dp[i][j] = arr[i][j] + dp[i-1][j];
            }
            else{ //j가 0이 아닐때의 경우
                dp[i][j] = max((arr[i][j]+dp[i-1][j]),(arr[i][j] + dp[i-1][j-1]));
                dp[i][j] = max(dp[i][j],(arr[i][j]+dp[i][j-1]));
            }
            }
 
        }
 
 
    cout << dp[n-1][m-1];
}