백준 11048 - 이동하기

문제

 

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

11048번: 이동하기

 

 

풀이

 

(1,1)에서 (N,M)까지 이동해야 하는 문제이고 이동가능한 방향은 오른쪽, 아래, 오른쪽 대각선 아래 방향 세 가지 경우이다. 이걸 반대로 생각하면 (i,j)로 이동할 수 있는 점은 (i, j-1), (i-1, j), (i-1, j-1) 세 가지가 된다. 이 세가지 경우 중에서 최대를 골라 (i, j)에 더해주면 (N,M)까지 이동하는 최대값이 된다. 이 과정을 (N,M)까지 이어 가면 된다.

 

 

코드

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int N, M;
int dp[1001][1001];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N >> M;
 
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++) 
            cin >> dp[i][j];
 
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++)
            dp[i][j] += max(dp[i-1][j-1], max(dp[i-1][j], dp[i][j-1]));
 
    cout << dp[N][M];
 
    return 0;
}