[BOJ/Gold 4] 백준 1749 점수따먹기(C++)

문제 링크

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

1749번: 점수따먹기

 

문제

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

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

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

입력

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

출력

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

예제 입력 1

3 5
2 3 -21 -22 -23
5 6 -22 -23 -25
-22 -23 4 10 2

예제 출력 1

16

알고리즘 분류

• 브루트포스 알고리즘
• 누적 합

풀이

2차원 배열의 누적 합을 구하고, 각 부분 배열마다 다 탐색해서 배열의 합의 최댓값을 구한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 201
#define LL long long
#define INF 1e9

using namespace std;
int N, M;
int MAP[MAX][MAX];
int Sum[MAX][MAX];
int Answer = -INF;

void Input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> MAP[i][j];
		}
	}
}

void Settings() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			Sum[i][j] = MAP[i][j] + Sum[i][j - 1] + Sum[i - 1][j] - Sum[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++) {
					int Cur = Sum[k][l] - Sum[k][j - 1] - Sum[i - 1][l] + Sum[i - 1][j - 1];
					Answer = max(Answer, Cur);
				}
			}
		}
	}
}

void Find_Answer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}