[BaekJoon/백준] 11048번 이동하기

 

DP로 문제를 해결했다.

DFS, BFS로 풀 수 있는 문제가 아니다. 1000 x 999 x 998 ... 엄청난 시간이 나올 것.

// 오른쪽, 아래, 오른쪽아래 움직일 수 있는 특성.
// 행 기준으로 '->' 순환하며 dp 하면 될 것 같다.
// 시간복잡도 O(n)

#include <iostream>
#define MAX(a,b) (a>=b?a:b)

using namespace std;

int N, M;
int Arr[1000][1000];
int DP[1000][1000];



int sx[3] = {0, -1, -1};
int sy[3] = {-1, 0, -1};

int tmp_x, tmp_y;

int main() {
    
    cin >> N >> M;
    
    
    for(int i = 0; i < N; i++) {
        
        for(int j = 0; j < M; j++) {
            
            cin >> Arr[i][j];
            
        }
    }
    
    DP[0][0] = Arr[0][0];
    
    
    for(int i = 0; i < N; i++) {
        
        for(int j = 0; j < M; j++) {
            
            
            for(int k = 0; k < 3; k++) {
                
                tmp_x = i + sx[k];
                tmp_y = j + sy[k];
                
                if(tmp_x < 0 || tmp_x > N || tmp_y < 0 || tmp_y > M)
                    continue;
                
                DP[i][j] = MAX(DP[i][j], (DP[tmp_x][tmp_y]+Arr[i][j]));
                
            }
        }
    }
    
    
    cout << DP[N-1][M-1] << "\n";

    
}