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

1749번 : 점수따먹기

---

문제)

동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점수 따먹기라는 게임인데 그다지 재밌어 보이지는 않는다.

 

동주가 개발한 게임은 이렇다. 일단 N*M 행렬을 그린 다음, 각 칸에 -10,000 이상 10,000 이하의 정수를 하나씩 쓴다. 그런 다음 그 행렬의 부분행렬을 그려 그 안에 적힌 정수의 합을 구하는 게임이다.

 

동주가 혼자 재밌게 놀던 중 지나가는 당신을 보고 당신을 붙잡고 게임을 하자고 한다. 귀찮은 당신은 정수의 합이 최대가 되는 부분행렬을 구하여 빨리 동주에게서 벗어나고 싶다.

 

 

 

입력 :

첫째 줄에 N (1 < N < 200), M (1 < M < 200)이 주어진다. 그 다음 N개의 줄에 M개씩 행렬의 원소가 주어진다.

 

 

 

 

출력 :

첫째 줄에 최대의 합을 출력하라.

 

 

 

 

 

풀이)

 

// 1749. 점수 따먹기
#include <iostream>
#include <vector>
#include <limits.h>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    vector<vector<long long>> vec(n + 1, vector<long long>(m + 1, 0));
    vector<vector<long long>> prefix(n + 1, vector<long long>(m + 1, 0));
 
    // 원본 배열 입력
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < m + 1; j++)
        {
            cin >> vec[i][j];
        }
    }
 
    // 누적합 배열을 만든다.
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < m + 1; j++)
        {
            prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + vec[i][j];
        }
    }
 
    long long answer = LLONG_MIN;
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < m + 1; j++)
        {
            for (int k = i; k < n + 1; k++)
            {
                for (int l = j; l < m + 1; l++)
                {
                    long long result = prefix[k][l] - prefix[i - 1][l] - prefix[k][j - 1] + prefix[i - 1][j - 1];
                    answer = max(answer, result);
                }
            }
        }
    }
 
    cout << answer;
 
    return 0;
}

---

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

1749번: 점수따먹기