[백준] 11660번 구간 합 구하기 5 (C++) - 간단한 dp

2. 소스코드

 1. 전체 소스코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
int arr[1025][1025] = {0, };
int dp[1025][1025] = {0, };

int main(){
	cin.tie(NULL); ios::sync_with_stdio(false);
	cin >> N >> M;
	
	for(int i=1; i<N+1; i++){
		for(int j=1; j<N+1; j++){
			cin >> arr[i][j];
		}
	}
	
	for(int i=1; i<N+1; i++){
		for(int j=1; j<N+1; j++){
			if(i==1 && j==1) dp[i][j] = arr[i][j];
			else{
				dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + arr[i][j];
			}
		}
	}
	
	for(int i=0; i<M; i++){
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		cout << dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] <<"\n";
	}
}

arrr[1025][1025]와 dp[1025][1025] 두 배열을 선언하고 (global), 이 배열에 대해 arr에는 입력되는 배열의 값을, dp[i][j]에는 (i, j)까지의 사각형 안 모든 숫자의 합을 저장하였다.

 

dp[i][j] = dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1] + arr[i][j] 식을 이용.  

그 원리는 아래 그림과 같다. (알분설 1주차 마지막 알고리즘 때 설명)