점수따먹기 1749

문제

접근 방법

2차원 누적 합을 활용하면 된다.
가로로 누적 합을 진행한 뒤 세로로 누적 합을 진행하면 누적 합이 완성된다. 사용 방법은 이러하다.

더하기			빼기
	시작
빼기			끝

시작과 끝을 재단하기 위해 제외되는 지점을 빼준다. 빼는 지점의 겹치는 지점(시작 지점의 대각선)을 다시 더하면 된다.

코드

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, M, ret = INT_MIN;
    cin >> N >> M;
    vector<vector<int>> matrix(N + 1, vector<int>(M + 1));
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= M; ++j)
        {
            cin >> matrix[i][j];
            matrix[i][j] += matrix[i][j - 1];
        }
    }
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            matrix[i][j] += matrix[i - 1][j];
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            for (int k = i + 1; k <= N; ++k)
                for (int l = j + 1; l <= M; ++l)
                {
                    int sum = matrix[k][l] - matrix[i][l] - matrix[k][j] + matrix[i][j];
                    ret = sum > ret ? sum : ret;
                }
    cout << ret;
    return 0;
}

풀이

누적 합을 하고 난 뒤에는 최대가 되는 부분 행렬을 찾아주면 된다.
그 부분은 완전 탐색으로 해결하면 된다.

실수로 반환해야 하는 값의 초기를 0으로 했었는데 음의 수도 최대의 합이 될 수 있기에 0이 아닌 최솟값으로 정해주는 것이 좋다. 이 부분에서 실수하면 100%에서 틀린다.