Beakjoon 1520 내리막 길

21 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/1520

나의 풀이

이 문제는 DP와 DFS 문제를 결합한 문제이다. 먼저 DP를 정의하면 다음과 같다.
DP[i][j] = (j, i)에서 목표 지점까지 갈 수 있는 경우의 수
예를 들어 지도가 다음과 같이 주어질 때를 생각해보자

50	32	30
30	30	25
27	15	10

최종 지점이 (2,2)이기 때문에 DP[2][2] = 1이다.
우리가 최종적으로 구해야하는 값은 (0,0)에서 목표 지점까지 갈 수 있는 경우의 수이기 때문에 DP[0][0]을 구해야한다.
DP[0][0]을 구하기 위해서는 (0, 0)에서 이동할 수 있는 좌표 (x, y)를 찾아 그 위치에서 목표 지점까지 갈 수 있는 모든 경우의 수를 더해주면 된다. 위 예시의 경우 (x, y)가 (1, 0), (0, 1) 두가지 경우가 될 수 있고, DP[0][0] = DP[0][1] + DP[1][0]이 된다. 하지만 DP[0][1]과 DP[1][0] 또한 아직 구하지 못했기 때문에 DP[0][1]과 DP[1][0]을 구해야 한다.
먼저 DP[1][0]은 (0, 1)에서 이동할 수 있는 좌표가 (0, 2)뿐이기 때문에 DP[1][0] = DP[2][0]이 된다. 마찬가지로 DP[2][0]의 값은 아직 구하지 못했기 때문에 DP[2][1]를 구해야 하고, DP[2][1] = DP[2][2] = 1이 된다. 정리하면 다음과 같다.
DP[1][0] = DP[2][0] = DP[2][1] = DP[2][2] = 1
이제 같은 방식으로 DP[0][1]를 구하면
DP[0][1] = DP[1][1] + DP[0][2] = (DP[2][1] + DP[1][2]) + (DP[1][2]) = (1 + DP[2][2]) + DP[2][2] = (1+1) + 1 = 3
여기서 DP[2][1]은 이미 구했었기 때문에 그 값을 사용한다.
최종적으로 DP[0][0]은 다음과 같은 값을 얻을 수 있다.
DP[0][0] = DP[1][0] + DP[0][1] = 1 + 3 = 4
이렇듯 이 문제는 Top-down 방식의 DP로 문제를 해결할 수 있다.
구현할 때 아직 DP값을 구하지 않았다는 것을 의미하기 위해 DP[i][j]의 초기 값을 -1로 초기화 하였다.

풀이 코드 : 1520 내리막 길

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

long long DP[500][500];
int M, N;
vector<vector<int>> map;
int X[] = {0, 0, 1, -1};
int Y[] = {1, -1, 0, 0};

int DFS(int x, int y){
    int new_x, new_y;
    if(DP[y][x] != -1) return DP[y][x];
    DP[y][x] = 0;
    for(int i=0;i<4;i++){
        new_x = x + X[i];
        new_y = y + Y[i];
        if(new_y < M && new_x < N && new_y >= 0 && new_x >= 0 && map[y][x] > map[new_y][new_x]){
            DP[y][x] += DFS(new_x, new_y);
        }
    }
    return DP[y][x];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>M>>N;
    map.resize(M);
    for(int i=0;i<M;i++){
        map[i].resize(N);
        for(int j=0;j<N;j++){
            cin>>map[i][j];
            DP[i][j] = -1;
        }
    }

    DP[M-1][N-1] = 1;
    DFS(0,0);

    cout<<DP[0][0];

}

채점결과