[BOJ] 1520번: 내리막 길

1520번: 내리막 길

풀이

대표적인 동적 계획법 문제라고 한다. 처음엔 어떻게 DP로 풀지??라고 생각했지만 DP라는 방향을 잡고나니 풀기 상당히 쉬워졌다.

기준값: m == 0 && n == 0일 때는 1이다.
점화식…?인지는 모르겠지만 4방향을 돌면서 본인보다 큰지 작은지 확인하면 된다.

나는 탑-다운 방식으로 해서 풀었고 visited 배열까지 써서 풀었지만 사실 dp배열을 -1로 초기화 시키고 분기문을 하나 만들어서 풀면 visited 배열을 만들 필요가 없다고 한다.
참조

코드

#include <cstdio>

int dp[501][501], n, m;                         // dp[i][j]는 (0, 0)에서 (i,j)까지 가는 경우의 수
int map[501][501];                              // 입력 저장하는 곳.
bool visited[501][501];                         // 방문한 곳인지 확인하는 거
int drt[2][4] = {{-1, 0, 1, 0}, {0, 1, 0, -1}}; // drt[y][x]
bool inline safe(int y, int x)
{
    if ((0 <= y && y < m) && (0 <= x && x < n))
        return true;
    return false;
}

int f(int m, int n)
{
    // safe: true, map[i][j] < map[i - drx[0][i]][j - drx[1][i]] then, go.
    if (m == 0 && n == 0)
        return 1;
    if (dp[m][n])
        return dp[m][n];
    visited[m][n] = true;
    for (int i = 0; i < 4; ++i)
    {
        int yy = m - drt[0][i];
        int xx = n - drt[1][i];
        if (safe(yy, xx) && (map[m][n] < map[yy][xx]) && visited[yy][xx] == false)
        {
            dp[m][n] += f(yy, xx);
            visited[m][n] = false;
        }
    }
    return dp[m][n];
}

int main()
{
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            scanf("%d", &map[i][j]);
        }
    }
    printf("%d", f(m - 1, n - 1));
    return 0;
}