[백준] 11660번 구간 합 구하기5 (C++)

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

 

문제 설명

2차원 배열이 주어졌을 때, (y1,x1)부터 (y2,x2)까지의 합을 구하는 문제이다.

 

주요 로직

1. 누적합을 사용하는 것이다.
n의 범위가 1024까지이기에 이중 for문을 사용해서 문제를 풀면 시간 초과가 발생한다

 

• i행 j열의 누적합 구하기
  pfix[i][j]는 1행부터 i행까지, 1열부터 j열까지의 모든 수의 합을 구한 값이다.

pfix[i][j] = pfix[i-1][j] + pfix[i][j-1] - pfix[i-1][j-1] + arr[i][j];

 

• (y1,x1)부터 (y2,x2)까지의 합 구하기

pfix[y2][x2] - pfix[y1-1][x2] - pfix[y2][x1-1] + pfix[y1-1][x1-1]

 

정답 코드

#include <iostream>

using namespace std;

int n,m,x1,x2,y1,y2;
int arr[1030][1030], pfix[1030][1030];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> m;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cin >> arr[i][j];
			pfix[i][j] = arr[i][j] + pfix[i][j-1] + pfix[i-1][j] - pfix[i-1][j-1];
		}
	}
	
	while(m--){
		cin >> y1 >> x1 >> y2 >> x2;
		cout << pfix[y2][x2] - pfix[y1-1][x2] - pfix[y2][x1-1] + pfix[y1-1][x1-1] << "\n";
	}
	
	return 0;
}