[백준] 이동하기 11048번 (c++)

출처 : https://www.acmicpc.net/problem/11048

11048번: 이동하기

풀이 방법

동적 계획법으로 재귀 함수를 사용해 해결했다.

재귀 함수의 기저 조건으로

1. y, x 좌표가 모두 0이면 return board[0][0] 

2. y, x 좌표가 범위를 넘어가면 return 0 을 해서 선택되지 않도록 설정

3. dp[y][x] 가 -1 이 아닌 다른 값으로 설정되어 있으면 그 값을 리턴

3가지를 설정 했다.

위 3가지가 아닌 경우 재귀 함수를 호출해서 max(solve(y - 1, x - 1), max(solve(y, x -1), solve(y-1, x))) + board[y][x] 

가장 큰 값에서 board[y][x]를 dp[y][x]에 저장해 두고 이 값을 리턴하였다.

#include <bits/stdc++.h>
using namespace std;

int n, m;
int board[1001][1001];
int dp[1001][1001];

int solve(int y, int x) {
    if (y == 0 && x == 0) return board[y][x];
    if (y < 0 || x < 0 || y > n || x > m) return 0;
    if (dp[y][x] != -1) return dp[y][x];
    dp[y][x] = max(solve(y - 1, x - 1), max(solve(y, x -1), solve(y-1, x))) + board[y][x];
    return dp[y][x];
}

int main() {
    cin >> n >> m;
    memset(dp, -1, sizeof(dp));
    for (int i = 0;i < n;i++) {
        for (int k = 0;k < m;k++) {
            cin >> board[i][k];
        }
    }
    dp[0][0] = board[0][0];
    solve(n-1, m-1);
    cout << dp[n-1][m-1];
    return 0;
}