[누적합] 구간 합 구하기 5 - 백준 11660번

11660번: 구간 합 구하기 5

풀이

누적합 구하기

공식 : arr[i][j] = arr[i-1][j] + arr[i][j-1] + val - arr[i-1][j-1];

(위에 더한거 + 왼쪽 더한거 + 넣으려고 하는 값 - 중복되는 값)

구간합 구하기

공식 : arr[x2][y2] - arr[x2][y1-1] - arr[x1-1][y2] + arr[x1-1][y1-1];

(누적합 - 왼쪽 누적합 - 위 누적합 + 중복 누적합)

에러

! 삼중 for문 사용시 시간초과

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

    int y = y2 - y1 + 1;
    int x = x2 - x1 + 1;

    int total = 0;
    for(int j=0;j<x;j++){
        for(int k=0;k<y;k++) {
            // cout << arr[x1+j-1][y1+k-1] << "\n";
            total += arr[x1+j-1][y1+k-1];
        }
    }
    cout << total << "\n";
}

• (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000)
  • 100000 x 1024 x 1024 > 1초(1억)

OutOfBounds

int arr[1025][1025];

• index가 0을 건너뛰고 1부터 세는 관계로 최대 1024에서 +1을 해줘야함.

코드

#include <iostream>

using namespace std;

int N,M;
int arr[1025][1025];

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

    cin >> N >> M;
    int val;
    // 누적합 구하기
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=N;j++) {
            cin >> val;
            arr[i][j] = arr[i-1][j] + arr[i][j-1] + val - arr[i-1][j-1];
        }
    }

    int x1, y1, x2, y2;
    // 구간합 구하기
    for(int i=0;i<M;i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << arr[x2][y2] - arr[x2][y1-1] - arr[x1-1][y2] + arr[x1-1][y1-1] << "\n";
    }    
}