[백준] 11660번: 구간 합 구하기 5 C++ 풀이

접근:

일반적으로 계산하면 시간 초과가 뜨는 문제이다.

반복적으로 더해주는 작업을 하는 것이기 때문에

DP로 접근하여서 푸는 것이 적절해 보인다.

 

전략:

구간 합을 입력 받을 때 마다 (0,0) 부터 (x2,y2)를 구해주어 2차원 배열로 저장하고,

구간 합이 주어지면 구해준 구간 합의 조합{(0,0) ~ (x2,y2)}으로 해결해주면 된다.

(x1 - 1 , y1 - 1)	(x1 - 1,  y2)
(x2 , y1 - 1)	(x2 , y2)

 구하고자 하는 값이 (x1,y1)부터 (x2,y2) 까지의 구간 합 이므로,

(x2, y2) - (x1-1 ,y2) - (x2 ,y1-1) + (x1 - 1 , y1 - 1)  이런식으로 구해준 값으로 겹치는 영역을 빼고 더해주면

원하는 구간의 값이 나온다.

 

구현:

#include <iostream>
#define SIZE 1025
using namespace std;
int n,m ;
int summap[SIZE][SIZE];

int x[2],y[2];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >>n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int tmp;
            cin >> tmp;
            summap[i][j] = summap[i][j-1] +summap[i-1][j] - summap[i-1][j-1] +tmp;
        }
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<2;j++){
            cin >> x[j] >> y[j];
        }
        int sum =0;
        sum = summap[x[1]][y[1]] - summap[x[1]][y[0]-1] - summap[x[0]-1][y[1]] + summap[x[0]-1][y[0]-1];
        cout << sum << '\n';
    }
    return 0;
}