BOJ 백준/Class 4

백준 11659번, 구간 합 구하기 5(C, C++)

simun 2022. 1. 20. 19:54

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

 

11660번: 구간 합 구하기 5

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네

www.acmicpc.net

#include<iostream>

using namespace std;

int prefixsum[1025][1025] ={0};
int dp[1025][1025];

int main(){
    int x1;
    int x2;
    int y1;
    int y2;
    int N;
    int M;


    cin >> N >> M;

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            cin >> prefixsum[i][j];
            dp[i][j] = dp[i-1][j] + dp[i][j-1] -dp[i-1][j-1] + prefixsum[i][j];
        }
    }

    
    for(int i = 0; i < M; i++){
        cin>>x1>>y1>>x2>>y2;
        cout<<dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]<<'\n'; 
    }
    return 0;
}