백준 11048 이동하기

algorithm : DP

 

해설

dp [i][j] = (j, i)에 얻을 수 있는 최대의 사탕 개수

(2,2)를 예로 들었을 때 (1,1) 대각선에서 오는 경우, (1,2) 옆에서 오는 경우, (2,1) 위에서 오는 경우

3가지가 있다 이경우 중 가장 큰 값과 가지 위치에 값을 더하면 dp [i][j] 값을 구할 수 이러한 식으로 dp를 채우면서

마지막에 dp [N][M]을 출력하면 된다

#include<bits/stdc++.h>
#define LM 1000+10
#define INF 199999999
using LL = long long;
using namespace std;

int N,M;
int arr[LM][LM];
int dp[LM][LM];

void input(){
    scanf("%d %d",&N,&M);
    for(int i = 1 ; i <= N ; i++){
        for(int j = 1 ; j <= M ; j++)
            scanf("%d",&arr[i][j]);
    }
}

void DP(){
    for(int i = 1 ; i <= N ; i++){
        for(int j =  1 ; j <= M ; j++)
            dp[i][j] = max({dp[i - 1][j],dp[i][j - 1],dp[i - 1][j - 1]}) + arr[i][j];
    }
    printf("%d",dp[N][M]);
}

int main(){
    //freopen("input.txt","r",stdin);
    input();
    DP();
    return 0;
}