[Dynamic Programming] 숫자판 놀이

문제

숫자들이 2차원 배열에 있다. 가장 윗 행에서 가장 아래 행까지 내려올때 걸 쳐지는 길에 있는 숫자의 합이 가장 높은것을 찾아보자. 이 때 어느 한 cell에 서 다음 cell로 내려올 경우에는 바로아래, 왼쪽대각선아래, 오른쪽대각선 아 래로만 이동이 가능하다.

 

풀이방법

1. 2차원 배열을 입력받은 뒤, 해당 셀에서 최대 합을 저장할 DP테이블을 만든다.

2. 각 셀에서 최대 합 = 현재 값 + MAX( 1번 셀 , 2번 셀 , 3번 셀)

3. 위 2번을 반복하여 모든 셀에 대해 최대 합을 계산하고, 가장 아래 행의 최대값이 주어진 문제의 답이 된다.

 

 

코드

Python

matrix = [
    [3, 4, 9, -2, 2, 51, -23, 2, -1],
    [223, 7, 8, -11, 5, -99, 2, 3, -4],
    [2, 51, -23, -23, 6, 3, 2, 4, 5],
    [5, -99, 2, -1, 32, 2, 5, -99, 2],
    [6, 3, 3, -4, 2, -1, 6, 3, 3],
    [32, 2, 4, 5, 3, -4, 2, -1, 4],
    [4, 4, 23, 6, 2, -1, 3, -4, 34],
    [78, 32, 1, 7, 3, -4, -23, -23, 6],
    [-9, -10, 54, 8, 4, 5, 2, -1, 32]
]

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

    # DP 테이블을 0으로 초기화
    dp = [[0] * cols for _ in range(rows)]

    # 첫 번째 행은 해당 셀의 값이 최대 합
    for j in range(cols):
        dp[0][j] = matrix[0][j]

    # 두 번째 행부터는 위쪽 행에서 최대값을 선택하여 더해줌
    for i in range(1, rows):
        for j in range(cols):
            left_diag = dp[i - 1][j - 1] if j > 0 else 0
            up = dp[i - 1][j]
            right_diag = dp[i - 1][j + 1] if j < cols - 1 else 0
            dp[i][j] = matrix[i][j] + max(left_diag, up, right_diag)

    # 가장 아래 행에서의 최대값 반환
    return max(dp[rows - 1])



max_sum = find_max_sum(matrix)
print("최대 합:", max_sum)

 

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    // DP 테이블 초기화
    vector<vector<int>> dp(rows, vector<int>(cols, 0));

    // 첫 번째 행은 해당 셀의 값이 최대 합
    for (int j = 0; j < cols; ++j) {
        dp[0][j] = matrix[0][j];
    }

    // 다음 행부터는 위쪽 행에서 최대값을 선택하여 더해줌
    for (int i = 1; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            int left_diag = (j > 0) ? dp[i - 1][j - 1] : 0;
            int up = dp[i - 1][j];
            int right_diag = (j < cols - 1) ? dp[i - 1][j + 1] : 0;
            dp[i][j] = matrix[i][j] + max({left_diag, up, right_diag});
        }
    }

    // 가장 아래 행에서의 최대값 반환
    return *max_element(dp[rows - 1].begin(), dp[rows - 1].end());
}

int main() {
    vector<vector<int>> matrix = {
        {3, 4, 9, -2, 2, 51, -23, 2, -1},
        {223, 7, 8, -11, 5, -99, 2, 3, -4},
        {2, 51, -23, -23, 6, 3, 2, 4, 5},
        {5, -99, 2, -1, 32, 2, 5, -99, 2},
        {6, 3, 3, -4, 2, -1, 6, 3, 3},
        {32, 2, 4, 5, 3, -4, 2, -1, 4},
        {4, 4, 23, 6, 2, -1, 3, -4, 34},
        {78, 32, 1, 7, 3, -4, -23, -23, 6}
    };

    int maxSum = findMaxSum(matrix);
    cout << "최대 합: " << maxSum << endl;

    return 0;
}