백준 11660 - 구간 합 구하기 5

 

안녕하세요 besforyou입니다 

 

---

문제 풀이

 

구간합을 새로운 좌표를 읽어들일때마다 새로 만들면 시간 초과가 생긴다. 그러니 누적합을 구해서 2차원 배열에 누적합을 저장해놓고, x1,y1 / x2, y2 좌표를 입력받을때마다 알맞은 누적합을 출력하면 된다.

 

 

 

1. 2차원 배열에 누적합을 저장

 

1 <= N <= 1024 이므로 행과 열의 길이가 1025인 2차원 배열 mat을 선언하자.

 

선언하고 입력받은 N만큼 2차원 배열의 원소 i, j에 mat[i][j-1] 값과 mat[i-1][j]값을 뺀 뒤 mat[i-1][j-1]과 i,j번째 입력값을 더해주면 해당 인덱스의 누적값을 알 수 있다.

 

2. 알맞은 누적합을 출력

 

위와 비슷하게 x1 - 1, y2 까지의 누적합과 x2 , y1 -1 까지의 누적합을 x2,y2까지의 누적합에서 뺀 뒤, x1 -1, y1 -1까지의 누적합을 다시 더해준값을 출력하면 된다.

 

코드

 

 

#include <iostream>
using namespace std;
 
int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m, x;
    int x1, x2, y1, y2;
    int sum[1025][1025];
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> x;
            sum[i+1][j+1] = x + sum[i+1][j] + sum[i][j+1] - sum[i][j];
        }
    }
 
    for (int i = 0; i < m; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << sum[x2][y2] - (sum[x1 - 1][y2] + sum[x2][y1 - 1]) + sum[x1 - 1][y1 - 1] << "\n";
    }
 
    return 0;
}