이번 문제도 전에 풀었던 부분 합 구하기 문제와 비슷한 방법으로 부분 합을 구해 풀어야 시간초과가 발생하지 않는 문제이다. NxN 형식이라 공식을 찾아내는데 조금 힘들었다.

• psum[i][j]=psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1]+arr[i][j]; 이러한 공식으로 psum을 구했다.
• 결과 값은 psum[x2][y2]-psum[x1-1][y2]-psum[x2][y1-1]+psum[x1-1][y1-1] 이러한 공식으로 구했다.
• 이렇게 해도 endl을 사용하면 시간 초과가 발생하므로 줄 띄기는 '\n'을 사용해준다.

Code

#include <iostream>
#define MAX 1025
using namespace std;

int n, m;
int arr[MAX][MAX];
int psum[MAX][MAX];
int x1,y1,x2,y2;

void Input(){
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin>>arr[i][j];
            psum[i][j]=psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1]+arr[i][j];
        }
    }
}

int Solution(int x1, int y1, int x2, int y2){
    return psum[x2][y2]-psum[x1-1][y2]-psum[x2][y1-1]+psum[x1-1][y1-1];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    for(int i=0; i<m; i++){
        cin>>x1>>y1>>x2>>y2;
        cout<<Solution(x1,y1,x2,y2)<<'\n';
    }
    return 0;
}