[LeetCode] 1594 Maximum Non-Negative Product in a Matrix (C/C++)

문제

https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix

풀이

문제를 읽고 마지막 칸의 값은 이전 칸의 결과에 영향을 받는다는 것을 알 수 있었다. 마찬가지로 이전 칸의 값은 그 이전 칸의 전 칸의 결과에 따라 달라질 수 있다. 각 누적 결과가 이후 결과에 영향을 미치므로 동적 계획법으로 풀어야겠다고 생각했다.

다만, 마지막 칸의 값이 음수일 경우, 이전 칸의 값이 음수이면서 절대값이 가장 큰 값이 되어야한다. 이를 어떻게 구현할까 하다 최소값과 최대값을 모두 상태로 저장하는 방식으로 구현했다.

최소/최대 로직만 가져가면 15x15 크기의 행렬이므로 동적 계획법이 아니더라도 완전 탐색으로도 충분히 2억 번의 연산 안으로 해결할 수 있을 것 같긴하다.

정답 코드

C++17

#define MOD 1000000007

class Solution {
private:
    enum { MIN = 0, MAX = 1 };
    typedef std::array<long long, 2> State;
    typedef std::vector<std::vector<State>> Table;

public:
    int maxProductPath(const std::vector<std::vector<int>> &grid) {
        const size_t M = grid.size();
        const size_t N = grid[0].size();
        Table table(M, std::vector<State>(N, { LLONG_MAX, LLONG_MIN }));

        table[0][0] = { grid[0][0], grid[0][0] };

        for (size_t i = 1; i < M; i++) {
            const long long value = table[i - 1][0][MIN] * grid[i][0];
            table[i][0] = { value, value };
        }
        for (size_t j = 1; j < N; j++) {
            const long long value = table[0][j - 1][MIN] * grid[0][j];
            table[0][j] = { value, value };
        }

        for (size_t i = 1; i < M; i++) {
            for (size_t j = 1; j < N; j++) {
                const State &up = table[i - 1][j];
                const State &left = table[i][j - 1];
                State &current = table[i][j];

                for (const State &prev: { up, left }) {
                    for (const long long value: prev) {
                        current = {
                            std::min(current[MIN], static_cast<long long>(value) * grid[i][j]),
                            std::max(current[MAX], static_cast<long long>(value) * grid[i][j])
                        };
                    }
                }
            }
        }

        return table[M - 1][N - 1][1] < 0 ? -1 : table[M - 1][N - 1][1] % MOD;
    }
};

[LeetCode] 1594 Maximum Non-Negative Product in a Matrix (C/C++)

문제

풀이

정답 코드

Share this post