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

풀이 방법 : 누적 합

각 행의 각 좌표까지의 누적 합을 구해놓고 반복문을 돌리면서 각 시작 지점 위치에서 1 x 1 부터 시작해서 가능한 최대 크기의 부분 행렬들의 요소들의 합들을 구해주었다.

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

int Sums[201][201] = {};
int Max = INT_MIN;

int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int N, M;
    cin >> N >> M;

    for (int i = 1; i <= N; ++i)
    {
        int Sum = 0;
        for (int j = 1; j <= M; ++j)
        {
            int Num;
            cin >> Num;
            Sum += Num;

            Sums[i][j] = Sum;
        }

    }

    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= M; ++j)
        {
            for (int w = 0; w <= M - j; ++w)
            {
                int Sum = 0;

                for (int h = 0; h <= N - i; ++h)
                {
                    int TempSum = Sums[i + h][j + w] - Sums[i + h][j - 1];

                    Sum += TempSum;
                    Max = max(Sum, Max);
                }
            }
        }
    }

    cout << Max;
}