백준 11660번: 구간 합 구하기 5

문제

문제 바로가기> 백준 11660번: 구간 합 구하기 5

풀이

다이나믹 프로그래밍을 이용해서 풀었다. 먼저 아래와 같이 구간합을 구해놓고 포함되지 않는 부분(red)을 뺀 후 두번 빠진 부분(green)은 다시 한 번 더해주었다.

#include<iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, x; cin>>n>>m;
    int dp[n+1][n+1] = {};
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++) {
            cin>>x;
            dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + x;
        }
    }
    int x1, y1, x2, y2;
    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';
    }
}