백준 11660 - 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

 

고려사항

• 입출력 시간 줄이기...cstdio printf scanf 를 쓰거나, sync_with_false 를 쓰는 습관을 들여야하는데...
  (사실 여지껏 응시한 코테에서는 위와 같은 제한 사항은 없다...)
• x줄에서 각각의 y 좌표까지의 구간합 정보를 memo 에 저장한다.
• 41 - 45 라인의 방식으로 정답 도출.

 

#include <iostream>
using namespace std;

int board[1025][1025];
int memo[1025][1025];

int dp(int x, int y){
    int &v = memo[x][y];

    if(y == 0){
        return 0;
    }

    if(v != 0){
        return v;
    }

    for(int i=1;i<=y;++i){
        v += board[x][i];
    }

    return v;
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    int n, m, x1, x2, y1, y2, sum;
    cin>>n>>m;

    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cin>>board[i][j];
        }
    }

    for(int i=0;i<m;++i){
        cin>>x1>>y1>>x2>>y2;

        sum = 0;
        for(int j=x1;j<=x2;++j){
            sum += (dp(j, y2) - dp(j, y1-1));
        }
        cout<<sum<<"\n";
    }
    return 0;
}