[백준] 1749 - 점수따먹기

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

1749번: 점수따먹기

 

2차원 행렬에서의 누적합을 이용하는 문제이다.

먼저 누적합 배열 sum을 채워 넣어보자.

(1, 1)부터 (i, j)까지의 직사각형의 누적합을 나타내는 sum[i][j]는 어떻게 구할 수 있을까?

바로 sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];

마지막에 -sum[i - 1][j - 1]을 하는 이유는, sum[i - 1][j], sum[i][j - 1]에서 각각 sum[i - 1][j - 1]이 두 번 더해져 중복이 되었기 때문이다.

그렇다면 이제 누적합 배열 sum은 완성되었다.

 

그렇다면 브루트포스로 모든 구간의 누적합을 구해서 최댓값을 구해야 한다.

우리가 만든 sum을 이용해서 (startx, starty) 에서 (endx, endy)까지 직사각형의 누적합을 어떻게 구할 수 있을까?

바로 sum[endx][endy] = sum[endx][endy] - sum[startx][endy] - sum[endx][starty] + sum[startx][starty]이다.

이것도 마찬가지로 sum[startx][starty]가 두 번 빼지기 때문에 한 번 더해주어서 균형을 맞추었다.

 

이 문제는 주의 깊게 생각하지 않으면 100%에서 WA를 맞을 수 있다.

바로 i1과 j1의 범위이다. 처음에 본인은 i1을 [0, i], j1을 [0, j]로 설정하고, 100%에서 WA를 맞았다.

이유를 생각해 보니, 모든 원소가 음수가 들어오는 경우이다. 이 경우,

i == i1, j == j1일 경우에 누적 합(부분 배열)이 존재하지 않아 계산하는 부분의 결과가 0이 되어서 모든 원소가 음수인데도 최댓값이 0이 되는 경우가 생긴다.

따라서 i == i1, j == j1인 경우를 제외해야 한다.

 

#include <iostream>
#include <climits>
using namespace std;

int n, m, a[201][201], s[201][201];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> a[i][j];
			s[i][j] = a[i][j] + s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1];
		}
	}
	int ans = INT_MIN;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			for (int i1 = 0; i1 < i; i1++)
			{
				for (int j1 = 0; j1 < j; j1++)
				{
					ans = max(ans, s[i][j] - s[i1][j] - s[i][j1] + s[i1][j1]);
				}
			}
		}
	}

	cout << ans;
}