백준 1749 점수따먹기 (C++)

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

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> arr;
vector<vector<int>> prefix;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    int ans = -987654321;
    cin >> n >> m;

    arr.resize(n + 1, vector<int>(m + 1));
    prefix.resize(n + 1, vector<int>(m + 1));

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            prefix[i][j] = arr[i][j] + prefix[i][j - 1] + prefix[i - 1][j] - prefix[i - 1][j - 1];
        }
    }


    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = i; k <= n; k++) {
                for (int l = j; l <= m; l++) {
                    ans = max(ans, prefix[k][l] + prefix[i - 1][j - 1] - prefix[k][j - 1] - prefix[i - 1][l]);
                }
            }
        }
    }

    cout << ans;



    return 0;
}

1. 문제

n*m의 행렬이 주어질 때, 해당 행렬의 부분행렬 합의 최댓값을 구하라. 각 행렬의 값은 -10,000 이상 10,000 이하이다.

2. 풀이

행렬의 부분합은 누적합을 사용하여 구할 수 있다. 행렬에 음수가 들어갈 수 있으므로 모든 경우의 수를 탐색해야 한다.

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            prefix[i][j] = arr[i][j] + prefix[i][j - 1] + prefix[i - 1][j] - prefix[i - 1][j - 1];
        }
    }

입력받은 행렬 값을 가지고 행렬의 누적합을 구해준다.

    int ans = -987654321;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = i; k <= n; k++) {
                for (int l = j; l <= m; l++) {
                    ans = max(ans, prefix[k][l] + prefix[i - 1][j - 1] - prefix[k][j - 1] - prefix[i - 1][l]);
                }
            }
        }
    }

그후 arr[i][j]~arr[k][l] 까지의 누적 합을 모두 구해준 후 ans 값을 갱신해준다.

연산이 끝나고 ans를 출력하면 정답을 구할 수 있다.