[BOJ] 11660 : 구간 합 구하기 5(코드개선) - travelbeeee

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

---

[ 알고리즘풀이 ]

( 기존풀이 : https://travelbeeee.tistory.com/288 )

DP[ i ][ j ] : (1, 1) ~ (i , j) 까지 구간의 합. 이라고 정의하면 다음과 같은 점화식이 성립합니다.

DP[i][j] = DP[i - 1][j] + DP[i][j - 1] - DP[i - 1][j - 1] + map[i][j]

#include<iostream>

using namespace std;
int N, M, a, b, c, d, map[1025][1025] = {}, DP[1025][1025] = {};

int main(void) {
	ios::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 >> map[i][j];
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			DP[i][j] = DP[i - 1][j] + DP[i][j - 1] + map[i][j] - DP[i - 1][j - 1];

	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c >> d;
		cout << DP[c][d] - DP[c][b - 1] - DP[a - 1][d] + DP[a - 1][b - 1] << '\n';
	}
	return 0;
}

 

---