백준 11048번 - 이동하기

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

N제한이 1000까지 있어서 입력받는 데만 O(N^2)의 시간이 걸린다.
dp를 통해서 문제를 해결해야 한다.


입력을 받을 때 마다 dp[i][j]의 값을 업데이트 해야 하는데
가져갈 수 있는 사탕의 최대값은 (i,j)의 사탕 개수에서 
(i-1,j) / (i,j-1) / (i-1,j-1)의 사탕 개수의 최대값을 더해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
    
    int N,M;
    cin>>N>>M;
    
    vector<vector<int>> dp(N+1,vector<int>(M+1,0));
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++){
            scanf("%d",&dp[i][j]);
            dp[i][j]+=max(dp[i-1][j-1],max(dp[i-1][j],dp[i][j-1]));
        }
    
    cout<<dp[N][M]<<endl;
    return 0;
}