[백준] 11660. 구간 합 구하기 5

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

28068

13432

10515

46.829%

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

 

실버 1 누적합 문제입니다.

2차원 누적합 배열을 작성해야합니다.

2차원 누적합 배열을 작성할 때 시간초과가 나지않도록 작성해야합니다 

psum[i][j]=psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1]+arr[i][j]

 

	#include<bits/stdc++.h>

	using namespace std;
	int arr[1025][1025];
	int psum[1025][1025];
	int n;
	void PSUM() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				psum[i][j] = psum[i - 1][j] + psum[i][j - 1] - psum[i - 1][j - 1] + arr[i][j];
			}
		}
	}
	int CAL(int x1, int y1, int x2, int y2) {
		int ret = psum[x2][y2];
		if (x1 > 0)ret -= psum[x1-1][y2];
		if (y1 > 0)ret -= psum[x2][y1 - 1];
		if (x1 > 0 && y1 > 0)ret += psum[x1-1][y1-1];

		return ret;
	}
	int main() {
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);
		memset(psum, 0, sizeof(psum));
		int m, x, x1, x2, y1, y2;
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> x;
				arr[i][j] = x;
			}
		}
		PSUM();
		for (int i = 0; i < m; i++) {
			cin >> x1 >> y1 >> x2 >> y2;
			cout << CAL(x1, y1, x2, y2) << "\n";
		}
	}

PSUM 함수는 누적합 배열을 작성하는 함수고,

CAL 함수는 답을 반환하는 함수입니다.