1520번

1520번 - 내리막 길

전형적인 DP문제인데 한가지 조심해야 할 점은 , 바로 memoization 의 초기값 설정이었다.

보통 0이나 -1 로 선택해서 하게 되는데,

나 같은 경우에는 캐시에 값을 더해주는 문제의 경우에는 0을 주로 사용하긴 한다. (그래야 값이 변하지 않으므로)

근데 이 문제에서는 더 이상 갈 수 없는 경로가 존재하기 때문에 캐시값이 0이 되는 경우가 발생한다.

따라서 초기에 캐시값 설정은 -1로 해주는 것이 좋다.

그런데 이제 문제는 값이 더해지는 문제이기 때문에 -1이 되어있으면 안된다는 점이었다.

즉, 캐시값에 값을 더하는 것인데 초기값이 0 이면 1을 더하든 2를 더하든 상관없지만, 초기값이 -1 이므로 1이나 2등을 더하면

원래 제값이 안나오게 된다. 그래서 방문한 지점을 0으로 만들어줘야 했다.

그런데 처음에 나는 0으로 초기화 하는 것의 위치를 잘못 지정해서 시간초과가 발생했었다.

( 0 초기화 과정을 for문 안의 if문에 넣었다. 그러다 보니 아무곳도 못가는 곳이 그대로 0으로 되어 있어서 계속 헛돌았다)

<정답 코드>

#include<iostream>
#include<string.h>
 
using namespace std;
 
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int map[501][501];
int D[501][501];
int N, M;
int go(int x, int y)
{
    if (x == N - 1 && y == M - 1)
    {
        return 1;
    }
 
    if (D[x][y] >=0)
    {
        return D[x][y];
    }
    
    if (D[x][y] == -1)
    {
        D[x][y] = 0;
    }
 
    for (int d = 0; d < 4; d++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (map[x][y] > map[nx][ny] && nx>=0 && ny>=0 && nx<N && ny<M)
        {
            
            D[x][y] += go(nx, ny);
        }
    }
 
    return D[x][y];
}
 
int main()
{
    cin >> N >> M;
    memset(D, -1, sizeof(D));
    
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
        }
    }
 
    printf("%d\n",go(0, 0));
 
    return 0;
}