[C++] BAEKJOON 1520 내리막길

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

1520번: 내리막 길

동적계획법을 사용한 문제입니다. dp[i][j] 을 (i,j) 에서 시작해서 (N,M) 까지 가는 경로의 수 라고 정의하였습니다. 이 문제 같은 경우에는 top-down 으로 접근할 경우, 필요없는 경로로의 접근을 막을 수 있기 때문에 이 방법을 취했습니다. dp 배열은 -1 로 초기화 해놓은 상태에서 다른 값이 존재하면 그 값을 참조하여 시간을 줄였습니다. (memorization)

 

#include <iostream>

using namespace std;

int N,M;
int board[501][501];
long long dp[501][501];

// 오른, 왼, 아래, 위
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

long long go(int x, int y){
    if (x==N-1 && y== M-1) return 1;
    if (dp[x][y] != -1){
        return dp[x][y];
    }

    dp[x][y]  = 0;

    for (int k=0;k<4;k++){
        int nx = x+dx[k];
        int ny = y+dy[k];
        if (0 <= nx && nx < N && 0 <= ny && ny < M){
            if (board[x][y] > board[nx][ny])
                dp[x][y] += go(nx,ny);
        }
    }
    return dp[x][y];
}


int main(int argc, const char * argv[]) {
    
    cin >> N >> M;
    
    for (int i=0;i<N;i++){
        for (int j=0;j<M;j++){
            cin >> board[i][j];
            dp[i][j] = -1;
        }
    }
    
    cout << go(0,0) << "\n";
    return 0;
}