[백준/Baekjoon] 1520 내리막 길 C++ :: Back Tracking & Dynamic Programming

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

1520번: 내리막 길

---

1. Logic

기본 DFS, 백트래킹 문제지만 시간복잡도때문에 메모이제이션을 활용하여 시간복잡도를 줄여줘야 한다. 즉 DFS와 DP를 합친 문제.

 

여기서 dp배열이 의미하는 것은 input[ny][nx]까지 갈 수 있는 경우의 수이다.

 

그리고 원래 DFS에서는 갔던 곳을 또 가지 않도록 무한루프에 빠지지 않도록 vis배열을 갱신해줘야 하지만 여기서는 항상 작은곳으로만 가기 때문에 vis배열을 갱신해 줄 필요가 없다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int n, m;
int vis[501][501];
vector<vector<int>> input(501, vector<int> (501, 0));
int dp[501][501];

int solve(int y, int x) {
    if(y == n - 1 && x == m - 1) return 1;
    int &ret = dp[y][x];
    if(dp[y][x] != -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 >= m || ny < 0 || ny >= n) continue;
        if(input[y][x] <= input[ny][nx]) continue;
        ret += solve(ny, nx);
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(dp, -1, sizeof(dp));

    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> input[i][j];
        }
    }

    cout << solve(0, 0);
}

 

 

---

3. Feedback

DFS까지는 잘 구현 했지만 시간초과가 나서 DP인 것을 알았다. 시간복잡도 계산을 잘못해서 DP인 것을 빠르게 알아차리지 못해서 풀이 낭비를 했다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐