[백준] 11660 구간 합 구하기 5 / DP (C++)

문제
N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력
총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

.
.
풀이

강의를 들으면서 한 번 풀어봤던 개념이라 쉽게 해결했다.
처음봤으면 감도 못 잡았을 듯...

기본적인 컨셉은 (1,1)부터 본인 좌표까지 사각형을 그렸을 때의 누적합을 기록하는 배열을 만들어주는것이다.
가로와 세로의 맨 첫줄을 채워준 뒤에,

4 = 1 + 2 - 3 + (4자리에 있는 값)을 계산 해주면 된다.
1번은 원래 3,1번 자리의 합이고
2번은 원래 3,2번 자리의 합이다. 그러므로 중복으로 더해진 3을 한 번 빼준다.

결과 값을 구하려면 입력된 좌표를 가지고 다시 네모를 그려준다.

노란색 네모 값의 합을 구하려면
누적합 배열에서
초록 동그라미 - 분홍 동그라미 - 주황 동그라미 + 파란 동그라미를 해주면된다.

#include <iostream>
using namespace std;

int nums[1025][1025];
// 누적합을 기록하는 배열
int dy[1025][1025];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M, x1, y1, x2, y2;
	cin >> N >> M;

	for (int i = 1; i <=N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> nums[i][j];
		}
	}
	// 기본 재료 투입
	for (int i = 1; i <= N; i++)
	{
		dy[1][i] = dy[1][i - 1] + nums[1][i];
		dy[i][1] = dy[i - 1][1] + nums[i][1];
	}
	
	for (int i = 2; i <= N; i++)
	{
		for (int j = 2; j <= N; j++)
		{
			// 왼쪽 + 위 - 왼쪽 대각선 위
			dy[i][j] = dy[i][j - 1] + dy[i - 1][j] - dy[i - 1][j - 1] + nums[i][j];
		}
	}

	for (int i = 0; i < M; i++)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		cout << dy[x2][y2] - dy[x2][y1 - 1] - dy[x1 - 1][y2] + dy[x1 - 1][y1 - 1] << "\n";
	}
	return 0;
}