백준 - 1520 내리막 길

[문제 링크]

DP문제이다. 경로 모든 경로의 수를 구하는 미로 찾기와 같은 문제랑 다를게 없는데, 거기서 내리막으로만 갈 수 있다는 조건만 주면 되는 문제이다.

맵의 끝에 도달하면 1을 반환하고, 아닐 경우 0을 반환하여 경로의 갯수를 구한다.

밑은 이를 구현한 코드이다.

#include <cstdio>
#include <cstring>
int m,n,arr[501][501];
int relPos[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int cache[501][501]; 
int dp(int y,int x){
    //기저사례 : 끝에 도달했으면 탈출 
    if(y==m && x==n) return 1;  
    int& ret = cache[y][x];
    if(ret!=-1) return ret;
    ret = 0;
    for(int c = 0; c<4; c++){
        int px = x + relPos[c][0];
        int py = y + relPos[c][1];
        //맵을 안넘어서고 내리막이면 
        if(px <=n && py<=m && px>=1 && py>=1&&arr[py][px] < arr[y][x])
            ret +=dp(py,px);
    }
    return ret;
} 
int main(){
    memset(cache,-1,sizeof(cache));
    scanf("%d %d",&m,&n);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&arr[i][j]);
        }
    }
    printf("%d",dp(1,1));
} 

경로 문제를 자주 보다보니 경로 문제는 이제 다 비슷비슷하다는 생각이 든다.