[BOJ] 구간 합 구하기-5 1160(C++) - 39 일차

문제

11660번: 구간 합 구하기 5

생각

다이내믹 프로그래밍

간단하게 생각하면 답이 나온다.

다만 입력값이 워낙 많아서 

ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

를 입력 해주자

코드

#include <iostream>
using namespace std;

const int MAXN = 1025;
int map[MAXN][MAXN] ={0, };
int dp[MAXN][MAXN] ={0, };

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n; cin >> n;
    int m; cin >> m;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> map[i][j];
        }
    }
    dp[1][1] = map[1][1];
    dp[1][2] = map[1][2];
    dp[2][1] = map[2][1];
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + map[i][j];
        }
    }

    while(m--) {
        int sty, stx;
        cin >> sty >> stx;

        int endy, endx;
        cin >> endy >> endx;

        int sum = 0;
        sum = dp[endy][endx] - dp[endy][stx - 1] - dp[sty - 1][endx] + dp[sty - 1][stx - 1];
        cout << sum << "\n";
    }
}