[백준/Baekjoon] 2167 2차원 배열의 합 C++ :: Prefix sum

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

2167번: 2차원 배열의 합

---

1. Logic

11066번 파일합치기 DP문제를 풀다가 누적합이라는 개념을 알게되어 공부할 겸 풀어봤다.

 

물론 이문제는 누적합 없이도 풀리긴 한다.

 

아래 행렬의 누적합을 구해보자

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

 

나는 처음에 행렬의 누적합은 당연히 다 1,1에서 해당 좌표까지 다 더하는 줄 알았다 그래서 내가 생각한 누적합은 아래와 같았다ㅋㅋㅋㅋ

y\x	1	2	3
1	1	3	7
2	15	31	63

얘 틀린겁니다.,,,

 

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

 

---

2. Code

누적합 풀이

#include<bits/stdc++.h>

using namespace std;

int n, m, k;

int arr[301][301];

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 <= m; j++) {
	        cin >> arr[i][j];
	    }
	}
	
	cin >> k;
	
	for(int i = 0; i < k; i++) {
	    int a, b, x, y;
	    cin >> a >> b >> x >> y;
	    
	    int sum = 0;
	    
	    for(int j = a; j <= x; j++) {
	        for(int l = b; l <= y; l++) {
	            sum += arr[j][l];
	        }
	    }
	    
	    cout << sum << '\n';
	}
}

브루트포싱 풀이

#include<bits/stdc++.h>

using namespace std;

int n, m, k;

int arr[301][301];

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 <= m; j++) {
	        cin >> arr[i][j];
	    }
	}
	
	cin >> k;
	
	for(int i = 0; i < k; i++) {
	    int a, b, x, y;
	    cin >> a >> b >> x >> y;
	    
	    int sum = 0;
	    
	    for(int j = a; j <= x; j++) {
	        for(int l = b; l <= y; l++) {
	            sum += arr[j][l];
	        }
	    }
	    
	    cout << sum << '\n';
	}
}

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