(c++) 동적계획법 BOJ 1520번: 내리막 길

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

1520번: 내리막 길

 

 

 

문제 개요

 

 

현재 위치보다 작은 상하좌우로 이동할 수 있는 것으로

 

재귀를 이용하여 시작 위치에서 끝 위치까지의 거리를 계산하면 되는 문제이다.

 

현재 위치보다 다음 위치가 작을 경우 현재 위치에 값을 더해주는 것으로 코드를 짜보았다.

 

함수에는 x, y가 끝 위치와 같다면 1을 리턴해주는 조건을 달아서

시작 위치인 (0, 0)에서 결괏값이 저장되도록 한다.

 

 

코드

 

 

위치 이동같은 경우 구현 문제와 마찬가지로

미리 x, y에 대한 이동 경로를 배열로 저장하고

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

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

 

함수 안에 반복문을 통해서

int nx = x + dx[i];

int ny = y + dy[i];

 

상하좌우 모든 경우를 따져볼 수 있게 된다.

#include <bits/stdc++.h>

using namespace std;
int n, m;
int map_n[500][500], cache[500][500];

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

int road(int x, int y) {
    int& ret = cache[x][y];
    if (x == m-1 && y == n-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 < m && ny >= 0 && ny < n) {
            if (map_n[nx][ny] < map_n[x][y]) {
                ret += road(nx, ny);
            }
        }
    }
    return ret;
}
int main(void) {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cin >> m >> n;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map_n[i][j];
        }
    }
    fill(&cache[0][0], &cache[499][500], -1);
    cout << road(0, 0);
}