표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.
입력
첫째 줄에 표의 크기 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)까지 합을 구해 출력한다.
✅ 문제 풀이
n을 입력 받고 나서 크기가 n+1*n+1인 2차원 벡터를 생성해준다.
그리고 배열의 첫번째 행은 사용하지 않을 것이고, 첫번째 열은 모두 0으로 초기화 해준다.
이 배열은 각 행마다의 누적 합을 갖도록 한다.
배열 값을 입력 받을 때, 해당 행과 열에 해당하는 값은, 배열값+이전열 값을 더하여 누적하도록 한다.
이렇게 누적합을 가진 배열을 가지고, m번의 좌표 입력을 받을 것이다.
좌표의 x1부터 x2까지, y2까지의 누적합에서 y1-1까지의 누적합을 뺀 결과를 누적하여 각각의 answer를 구하고 출력한다.
만약 x1=2, y1=2, x2=3, y2=4이면 누적합 배열의 2행부터 3행까지, 각 항의 4열까지의 누적합-1열까지의 누적합을 하면 2,3,4열을 합한 값이 되는 것이므로 반복적인 덧셈을 피할 수 있다.
이렇게 누적합은 반복적인 연산을 줄여주어서 시간복잡도를 낮추어주는 장점이 있다.
✏ 코드 전문
#include<iostream>
#include<vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
vector<vector<int>> sum(n+1, vector<int>(n+1));
for (int i = 1; i < n+1; i++) {
sum[i][0] = 0;
for (int j = 1; j < n+1; j++) {
cin >> sum[i][j];
sum[i][j] += sum[i][j - 1];
}
}
for (int i = 0; i < m; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int answer = 0;
for (int j = x1; j <= x2; j++) {
answer += (sum[j][y2] - sum[j][y1 - 1]);
}
cout << answer<<"\n";
}
return 0;
}
