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

문제 : https://www.acmicpc.net/problem/11660

C++

#include<iostream>
using namespace std;

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

    int n,m,x1,y1,x2,y2,count = 0;
    cin >> n >> m;

    int arr[n+1][n+1];
    int final[n+1][n+1];

    // prefix_sum[i] = prefix_sum[i-1] + arr[i] 1차원 배열
    /*
     1 2 3 4
     2 3 4 5
     3 4 5 6
     4 5 6 7

     2 2 3 4 (2,2) , (3,4) -> 27 3+4+5+4+5+6
     3 4 3 4 -> 6
     1 1 4 4 (1,1) , (4,4) -> 64

     (3,4) (2,2)
     prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] 겹친 부분
     - prefix[i-1][j-1] + arr[i][j]

     (3,4)에서
     */

    // 누적합을 먼저 지정해야놓아야함. 시간초과 우엑
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> arr[i][j];
            final[i][j] = final[i-1][j] + final[i][j-1] - final[i-1][j-1] + arr[i][j];
        }
    }

    // 3,4 합에서 - (1,4)랑 (3,1)빼고 두 번 뺴준 겹치는 부분 합친다
    while(m--) {
        cin >> x1 >> y1 >> x2 >> y2;
        count = final[x2][y2] - final[x1-1][y2] - final[x2][y1-1] + final[x1-1][y1-1];
        cout << count << "\n";
    }
}

문제풀이

• 문제를 처음 봤을 때, 이차원 배열에 대한 누적합 문제라고 생각했다. 일차원 배열과는 다르게 조금 복잡해보여서 직접 표를 그리고 지워가면서 공식을 도출해냈다. 누적합을 구하는 방법은 prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + arr[i][j]. 각 부분 더하고 겹치는 부분 마이너스. 그리고 해당 범위의 합을 구하는 방법은 final[x2][y2] - final[x1-1][y2] - final[x2][y1-1] + final[x1-1][y1-1]이다.

Comment

• 누적합 문제를 처음 풀어봐서 구간 합 구하기 4,5문제가 어렵다고 느껴졌던 것 같다. prefix 배열을 사용해서 푸는 방법은 거의 공식이라고 생각되서 외워야되겠다,,