[백준] 1520번 내리막 길 (C++)

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

 

 

이 문제는 N X M 행렬이 주어지고 각각의 요소가 주어질때 (1, 1)에서 시작하여 (N,M)까지 도달할 수 있는 경우의 수를 출력해야한다.

 

이때 한가지 조건은 현재 칸에서 다음 칸으로 갈때 작은 값으로 줄어들어야 한다.

 

이때 단순 재귀를 사용하여 경우의 수를 찾는 경우 O(2^NM)으로 지수승으로 값이 엄청나게 커진다.

 

따라서 이를 최적화할 수 있게 O(NM)으로 해결해야 한다.

따라서 dfs(깊이 우선 탐색) + dp(메모이제이션)을 사용하여 최적화하였다.

 

 

정답코드

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"

const int INF = 1e9;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N, M;
int graph[501][501];
int dp[501][501];
int answer;

int func(int x, int y) {
    int &ret = dp[x][y];

    if(x == N-1 && y == M-1) {
        return 1;
    }

    if(ret != -1) return ret;

    ret = 0;

    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;

        if(graph[nx][ny] < graph[x][y]) {
            ret += func(nx, ny);
        }
    }

    return ret;
}

void solve() {
    cout << func(0, 0);
}

void input() {
    cin >> N >> M;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> graph[i][j];

            dp[i][j] = -1;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}