[Dynamic Programming]치즈

문제

어떤 쥐가 p[n][m]로 구성된 미로에 있을 때 왼쪽 아래 즉, p[0][0]에서 시작하여 출구가 있는 p[n-1][m-1]에 도달하려고 한다.
단, 이 쥐는 항상 오른쪽 또는 위쪽으로만 움직일 수 있으며 치즈를 최대한 많이 먹으면서 출구로 이동하여야 한다

 

 

풀이방법

DP를 활용하여, 문제를 간단하게 풀 수 있다.

 

여기서 A[i][j]를 i행, j열까지 도달했을 때 먹을 수 있는 최대 치즈의 양이라고 정의하면, 다음과 같은 점화식을 사용하여 문제를 해결할 수 있다

 

A[i][j] = max(A[i][j-1], A[i-1][j]) + A[i][j]

• 현재 위치에서 왼쪽 칸 또는 위쪽 칸 중에서 더 많은 치즈를 먹을 수 있는 경우를 선택하여 현재 칸까지의 최대 치즈 양을 계산
• 이를 모든 칸에 대해 계산하면, 출구까지 도달했을 때 먹을 수 있는 최대 치즈의 양을 구할 수 있음

 

 

 

코드

Python

def max_cheese(matrix):
    rows = len(matrix)
    cols = len(matrix[0])

    
    dp = [[0] * cols for _ in range(rows)]

    # Initialize the first cell
    dp[0][0] = matrix[0][0]

    # 첫 번째 행은 왼쪽에서 넘어온 값으로만 갱신 가능
    for j in range(1, cols):
        dp[0][j] = dp[0][j - 1] + matrix[0][j]

    # 첫 번째 열은 아래에서 넘어온 값으로만 갱신 가능
    for i in range(1, rows):
        dp[i][0] = dp[i - 1][0] + matrix[i][0]

    #1행,1열을 제외한 행에 대해서 탐색
    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j]

    return dp[rows - 1][cols - 1]


matrix = [
    [0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 3],
    [1, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 1, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
]


print("Maximum cheese:", max_cheese(matrix))

 

C++

#include <iostream>
#include <vector>
using namespace std;

int max_cheese(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();

    vector<vector<int>> dp(rows, vector<int>(cols, 0));

    dp[0][0] = matrix[0][0];

    //첫 번째 행은 왼쪽에서 넘어온 값으로만 갱신 가능
    for (int j = 1; j < cols; ++j) {
        dp[0][j] = dp[0][j - 1] + matrix[0][j];
    }

    //첫 번째 열은 아래에서 넘어온 값으로만 갱신 가능
    for (int i = 1; i < rows; ++i) {
        dp[i][0] = dp[i - 1][0] + matrix[i][0];
    }

    //1행,1열을 제외한 행에 대해서 탐색
    for (int i = 1; i < rows; ++i) {
        for (int j = 1; j < cols; ++j) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
        }
    }

    return dp[rows - 1][cols - 1];
}

int main() {
    vector<vector<int>> matrix = {
        {0, 0, 1, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 1, 0, 0, 3},
        {1, 0, 0, 0, 0, 0, 0, 1, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0},
        {0, 1, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 1, 0, 0},
        {0, 1, 0, 0, 1, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 1, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0}
    };

    cout << "Maximum cheese: " << max_cheese(matrix) << endl;

    return 0;
}