[C++] 백준 11053: 구간 합 구하기 5

안녕하세요. 오늘 풀어볼 문제는 백준 구간합 구하기 5입니다.

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

 

이 문제는 구간 합 구하기 4의 심화버전이에요.

수행하는 기능은 간단하지만 테스트 케이스가 1개 이상이기 때문에 dp를 사용해야 합니다.

 

문제에서는 입력이 2차원 배열으로 주어지는데요,

각 행마다 dp를 적용하면 같은 x 값을 가지는 행들에서의 합을 구할 수 있겠죠.

그 합을 구하는 행의 범위에서 모두 더하면 구간 합을 구할 수 있습니다.

dp 배열은 0번부터 i번까지 원소들의 합으로 정의합니다.

만약 2번부터 5번까지의 합이 알고 싶다면 dp[5] - dp[1]로 구할 수 있어요.

dp[2]가 아닌 dp[1]을 빼는 이유는 dp[2]의 값도 포함되어야 하기 때문입니다.

 

#include <iostream>
using namespace std;

int N, M;
int input[1025][1025];
int dp[1025][1025];

int main() {
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> input[i][j];
			dp[i][j] = input[i][j] + dp[i][j - 1];
		}
	}

	for (int i = 0; i < M; i++) {
		int sum = 0;
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;

		for (int i = x1; i <= x2; i++)
			sum += dp[i][y2] - dp[i][y1 - 1];

		cout<< sum << '\n';
	}
}

 

도움이 되었다면 하트와 댓글 부탁드립니다.