[백준] 1520. 내리막 길 - C++

[Gold III]

 

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

1520번: 내리막 길

 

풀이 1

Bottom-Up 방식의 DP.

오른쪽 아래부터 왼쪽 위까지 채워나가는 방식으로 구현했다.

오른쪽과 아래로만 갈 수 있는 줄 알았는데, 위와 왼쪽으로도 갈 수 있어서 WA.

#include <algorithm>
#include <iostream>
#include <vector>
#define init cin.tie(0)->ios_base::sync_with_stdio(0);
 
typedef long long ll;
using namespace std;
 
int main() {
    init;
 
    int M, N;
    cin >> M >> N;
 
    int v[M + 1][N + 1];
    int h;
    for (int i = 1; i < M + 1; i++) {
        for (int j = 1; j < N + 1; j++) {
            cin >> h;
            v[i][j] = h;
        }
    }
 
    ll dp[M + 1][N + 1];
    fill(&dp[0][0], &dp[M][N], 0);
    dp[M][N] = 1;
    // 마지막 열
    for (int i = M - 1; i > 0; i--) {
        if (v[i + 1][N] < v[i][N]) dp[i][N] = 1;
    }
    // 마지막 행
    for (int j = N - 1; j > 0; j--) {
        if (v[M][j + 1] < v[M][j]) dp[M][j] = 1;
    }
 
    // dp
    for (int i = M - 1; i > 0; i--) {
        for (int j = N - 1; j > 0; j--) {
            // 오른쪽으로 갈 수 있는가
            if (v[i][j + 1] < v[i][j]) dp[i][j] += dp[i][j + 1];
            // 아래로 갈 수 있는가
            if (v[i + 1][j] < v[i][j]) dp[i][j] += dp[i + 1][j];
        }
    }
 
    cout << dp[1][1];
}

 

풀이 2

상하좌우 4방향으로 갈 수 있었기에, DFS를 이용해 Top-Down 방식으로 풀이했다.

상하좌우 중 갈 수 있는 지 확인한 후 재귀 호출. (line 20~23)

 

난이도에 비해 크게 어렵지 않았던 문제.

AC.

#include <algorithm>
#include <iostream>
#include <vector>
#define init cin.tie(0)->ios_base::sync_with_stdio(0);
 
typedef long long ll;
using namespace std;
 
int v[502][502];
ll dp[502][502];
int M, N;
 
int dfs(int i, int j) {
    if (i < 1 || i > M || j < 1 || j > N) return 0;
    if (i == M && j == N) return 1;
  	// Memoization
    if (dp[i][j] != -1) return dp[i][j];
 
    ll ret = 0;
    if (v[i][j] > v[i + 1][j]) ret += dfs(i + 1, j);
    if (v[i][j] > v[i][j + 1]) ret += dfs(i, j + 1);
    if (v[i][j] > v[i - 1][j]) ret += dfs(i - 1, j);
    if (v[i][j] > v[i][j - 1]) ret += dfs(i, j - 1);
 
    return dp[i][j] = ret;
}
 
int main() {
    init;
 
    cin >> M >> N;
 
    int h;
    for (int i = 1; i < M + 1; i++) {
        for (int j = 1; j < N + 1; j++) {
            cin >> h;
            v[i][j] = h;
        }
    }
    for (int i = 0; i < M + 2; i++) {
        v[i][N + 1] = 10001;
        v[i][0] = 10001;
    }
    for (int j = 0; j < N + 2; j++) {
        v[M + 1][j] = 10001;
        v[0][j] = 10001;
    }
 
    fill(&dp[0][0], &dp[M][N], -1);
 
    cout << dfs(1, 1);
}