백준 1520 / C++

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

1520번: 내리막 길

 

[ 풀이 ]

 

dp[i][j]를 (i,j)부터 출발할때 끝점에 도착하는 것의 개수라고 하자. 

기저조건은 dp[n-1][m-1]=1이다. 

dp[i][j]=∑ 4방향 dp[x][y] 이다. 

4방향중 높이조건을 위배하거나 칸을 벗어난다면 제외해주면 된다. 

답은 dp[0][0]이 된다. 

 

 

[ 코드 ] 

 

#include <bits/stdc++.h>
using namespace std;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int m, n, h[505][505], dp[505][505];

// 칸에 있는지 여부
int check(int x, int y) {
    return (x >= 0 && y >= 0 && x < n&& y < m);
}

// dp[i][j]
int go(int x, int y) {
    if (x == n - 1 && y == m - 1) return 1;
    int& ret = dp[x][y];
    if (ret != -1) return ret;
    ret = 0;
    // 4방향 합 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (check(nx, ny) && h[nx][ny] < h[x][y]) {
            ret += go(nx, ny);
        }
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> h[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    cout << go(0, 0) << '\n';
}