백준 11660 구간 합 구하기 5 (c++) : 피너클

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

11660번: 구간 합 구하기 5

구간합을 이용한 문제다.

long long sum[1025][1025];
long long ssum[1025][1025];
long long arr[1025][1025];

arr은 입력받을 배여르 ssum은 sum을 만들기 전 배열, sum은 2차원 배열의 구간합이다.

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		cin >> arr[i][j];
	}
}

arr을 입력받은 다음

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		ssum[i][j] = ssum[i][j - 1] + arr[i][j];
	}
}

ssum에 1차원 배열 구간합을 만들어준다.

예를 들어 ssum[0][2] = ssum[0][1] + arr[0][2]를 통해 ssum에는 점점 arr안의 숫자가 쌓이게 된다.

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		sum[j][i] = sum[j - 1][i] + ssum[j][i];
	}
}

그 다음 sum에 2차원 배열 구간합을 만들어준다.

ssum과 다른점은 가로가 아닌 세로 방향으로 만들어준다는 것이다.

sum[2][0] = sum[1][0] + ssum[2][0]과 같이 말이다.

while (m-- > 0) {
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	cout << sum[x2][y2] + sum[x1 - 1][y1 - 1] - sum[x1 - 1][y2] - sum[x2][y1 - 1] << endl;
}

마지막으로 x1, y1, x2, y2를 입력받은 다음 문제에서 원하는 구간의 합을 출력해준다.

파란색만큼의 구간합을 구하고 싶다면

전체에서

빨간색만큼 뺀다. 그러면 

파란색 부분만 남게 된다. 하지만 주황색 부분이 2번 빼졌으니 주황색 부분을 따로 더해준다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

long long sum[1025][1025];
long long ssum[1025][1025];
long long arr[1025][1025];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;

	memset(sum, 0, sizeof(sum));
	memset(ssum, 0, sizeof(ssum));

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ssum[i][j] = ssum[i][j - 1] + arr[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			sum[j][i] = sum[j - 1][i] + ssum[j][i];
		}
	}

	while (m-- > 0) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		cout << sum[x2][y2] + sum[x1 - 1][y1 - 1] - sum[x1 - 1][y2] - sum[x2][y1 - 1] << endl;
	}
}

전체코드다.