[백준/C++] 11048번: 이동하기

문제

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

---

문제 요약

N × M 크기의 미로는 1 × 1 크기의 방으로 나누어져 있다.

 

각 방에는 사탕들이 놓여져 있고, 방문할 때마다 모두 가져간다.

 

미로의 가장 왼쪽 윗 방에서 가장 오른쪽 아랫 방까지 이동할 때, 가져갈 수 있는 사탕 개수의 최댓값을 출력한다.

---

코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;

int arr[1010][1010];
int dp[1010][1010];

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

int res;

int dfs(int x, int y) {
    if (dp[x][y] != -1) {
        return dp[x][y];
    }
    if (x == n - 1 && y == m - 1) {
        return arr[x][y];
    }

    int max_score = 0;
    for (int d = 0; d < 3; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];

        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

        max_score = max(max_score, dfs(nx, ny));
    }

    return dp[x][y] = arr[x][y] + max_score;
}

int main() {
    
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            dp[i][j] = -1;
        }
    }

    cout << dfs(0, 0);
}

---

코드 설명

다이나믹 프로그래밍으로 문제를 해결한다.

 

dfs(x, y)는 (x, y) 방에서 가장 오른쪽 아랫 방까지 이동하면서 가져갈 수 있는 사탕의 최대 개수를 반환한다.dp[x][y]는 dfs(x, y) 값을 저장하는 메모이제이션 테이블이다.

 

dp[x][y] = (x, y) 방에 존재하는 사탕 개수 + 한 칸 이동한 방에서 오른쪽 아랫 방까지 이동하면서 가져갈 수 있는 사탕의 최대 개수