백준 11660번 구간 합 구하기 5

< 백준 11660번 구간 합 구하기 5 - 마포 코딩박 >

사용한 알고리즘: Prefix Sum ( 구간합 배열 )


 이차원 배열에서 구간합 배열을 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 5~6)
 'pSum[x][y]: x행의 1~y 열의 합' 이라고 설정해주었습니다.

(2) (코드 11~19)
 각 i 행별로 1~N의 열들의 값을 입력받으며 pSum[i][1~N] 값을 구해줍니다.

(3) (코드 19~26)
 입력받은 (x1, y1) ~ (x2, y2) 까지의 성분합을 계산하여 출력해줍니다.
 x1<=x<=x2 행들을 보면서 pSum[x][y2] - pSum[x][y1-1] 을 구해 더해주면됩니다.

	#include <bits/stdc++.h>
	using namespace std;
	int N, M;
	// pSum[x][y] : x행의 1~y 열 까지의 합
	int pSum[1026][1026];
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	for (int i = 1; i <= N; ++i){
	for (int j = 1; j <= N; ++j){
	int A;
	cin >> A;
	pSum[i][j] = pSum[i][j-1] + A;
	}
	}
	for (int i = 0; i < M; ++i) {
	int x1, y1, x2, y2;
	int sum = 0;
	cin >> x1 >> y1 >> x2 >> y2;
	for (int i = x1; i <= x2; ++i)
	sum += pSum[i][y2] - pSum[i][y1-1];
	cout << sum << '\n';
	}
	return 0;
	}

view raw BOJ 11660.cpp hosted with ❤ by GitHub