BOJ 1520 내리막 길

사용한 알고리즘

알고리즘 설명

DP를 정의하여 문제를 푼다.
DP는 2차원으로 정의는 다음과 같다.
DP(x,y): (x,y)좌표에서 내리막길로 (N,M)까지 가는 경로 경우의 수
DP(1,1)에서 부터 상하좌우중 내리막 조건이 만족하는 경로로 Sub-Problem를 해결해 간다.

풀이

// baekjoon 1520 yechan
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAX_N 502
#define INF 1e9
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

int N, M, data[MAX_N][MAX_N], dp[MAX_N][MAX_N];

int backtracking(int x, int y) {
    if (x == N && y == M) return 1;
    if (~dp[x][y]) return dp[x][y];

    int rst = 0;
    for (int d = 0; d < 4; ++d) {
        int nx = dx[d] + x, ny = dy[d] + y;
        if (data[nx][ny] && data[nx][ny] < data[x][y])
            rst += backtracking(nx, ny);
    }
    return dp[x][y] = rst;
}

int main() {
    scanf("%d%d", &N, &M);
    for (int i=1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            scanf("%d", &data[i][j]);
    memset(dp, -1, sizeof(dp));
    printf("%d\n", backtracking(1, 1));
    return 0;
}