[백준/Baekjoon] 11600 구간 합 구하기 C++ :: Prefix sum

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

11660번: 구간 합 구하기 5

---

1. Logic

먼저 이 문제를 풀기 위해서는 2차원 배열에서 누적합을 구하는 방법을 알아야 한다.

 

2차원 배열에서 누적합을 구하는 점화식을 먼저 보자

prefixSum[i][j] = prefixSum[i][j] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]

 

예시로 (2,2)의 누적합을 구하려면 

y\x	1	2	3
1	1	2	4
2	8	16	32

 

이 만큼의 칸들을 더해줘야 한다. 이걸 컴퓨터가 알아먹게 더하려면 아래와 같이 더해주면 된다.

먼저 원래 있던 (2,2)의 값인 16에 ( prefixSum[i][j] ) (1,1), (1,2)의 합인 prefixSum[i-1][j] 를 더해준다.

그리고 (1,1), (2,1)의 합인 (2, 1)도 더해준다.( prefixSum[i][j-1] ) 더하는 영역을 그림으로 보면 아래와 같다.

y\x	1	2	3
1	1	2	4
2	8	16	32

                   

y\x	1	2	3
1	1	2	4
2	8	16	32

 

 

 

 

 

 

 

 

 

 

하지만 이렇게 더하게 되면 (1,1)을 두번 중복해서 더하기 때문에 (1,1) 부분을 한번 빼줘야 한다. (  -prefixSum[i-1][j-1] )

y\x	1	2	3
1	1	2	4
2	8	16	32

 

이를 적용해서 이 문제에서는 parr에 누적합을 구해놓고 범위에 따라 구해주면 된다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int parr[1025][1025];

int n, m;

int main() {
    ios_base::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++) {
            cin >> parr[i][j];
            parr[i][j] += parr[i-1][j] + parr[i][j-1] - parr[i-1][j-1];
        }    
    }
    
    for(int i = 0; i < m; i++) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        
        cout << parr[y2][x2] - parr[y2][x1-1] - parr[y1-1][x2] + parr[y1-1][x1-1] << '\n';
    }
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90