[BOJ] 11660번 : 구간 합 구하기 5

1. problem : 

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

 

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
const int val = 1030; 
int board[val][val];
int d[val][val];
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	int n, m; 
	cin >> n >> m; 

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) cin >> board[i][j];
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) d[i][j] = d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1] + board[i][j];
	}

	while (m--) {
		int x1, y1, x2, y2; 
		cin >> x1 >> y1 >> x2 >> y2; 
		int ans = d[x2][y2] - d[x2][y1 - 1] - d[x1 - 1][y2] + d[x1 - 1][y1 - 1];
		cout << ans << '\n';
	}
}

dp를 이용해 풀었다. 따라서, 세 가지 스텝을 따른다. 

1. 테이블을 정의한다. d[i][j] 는 정해진 규칙에 의해 i번째 j번째 열까지의 합이다. 

2. 점화식을 작성한다. d[i][j] = d [i-1][j] + d [i][j-1] - d [i-1][j-1] + board [i][j]  

3. 초기값을 설정한다. d[0][모든열] = 0 , d [모든 행][0] = 0 ; 

 

이후 계산된 값을통해, 연산을 수행한다. 이때, int ans = d [x2][y2] - d [x2][y1-1] - d [x1-1][y2] + d [x1-1][y1-1]로 설정한다. ans를 int로 설정할 수 있는 이유는 합의 최댓값이 10억이기 때문이다.