문제

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

문제 링크

입력

첫째 줄에 표의 크기 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)까지 합을 구해 출력한다.

예제

예제 입력
4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

예제 출력
27
6
64

나의 접근 방법

구간 합을 미리 구해놓은 후 빼줘야 할 값들을 빼주고 중복되는 값을 더해주는 방식(Prefix Sum 활용)

예제의 입력 값인 2 2 3 4를 기준으로 생각해보자.
우리가 구하고 싶은 값은 (1,1)에서 (3,4)까지의 합을 구한 값에서 (1,1)에서 (1,4)까지의 합과 (1,1)에서 (3,1)까지의 합을 뺀 후 (1,1)에서 (1,1)까지의 합을 더한 값과 같다.
그림으로 보면 다음과 같다.
inputs

누적 합을 구해놓은 배열을 기준으로 보면 빨간 칸들의 값을 더한 값에서 파란 칸들의 값을 뺀 값이 정답이 된다.
prefix sum

코드

#include<iostream>
#include<vector>
using namespace std;
int main(void){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int N, M;
  cin>>N>>M;
  vector<vector<int>> arr(N+1, vector<int>(N+1, 0)), dp(N+1, vector<int>(N+1, 0));
  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++){
      dp[j][i] = dp[j-1][i] + arr[j][i];
    }
  }
  for(int i = 1 ; i<=N ; i++){
    for(int j = 1 ; j<=N ; j++){
      dp[i][j] = dp[i][j] + dp[i][j-1];
    }
  }
  for(int i = 0 ; i<M ; i++){
    int x1, x2, y1, y2;
    cin>>x1>>y1>>x2>>y2;
    cout<<dp[x2][y2]+dp[x1-1][y1-1]-dp[x1-1][y2]-dp[x2][y1-1]<<'\n';
  }
  return 0;
}

특이사항

input과 output이 많기 때문에 입출력 속도를 빠르게 해주지 않으면 시간 초과가 난다. 주의하자!