백준 11660 C++ - 구간 합 구하기5

Intro

문제풀이 및 소스코드

이 문제는 좌표 두개가 주어지고, 두 좌표사이 구간의 숫자합을 구하는 문제이다.

가장먼저 생각한것은 구간사이를 돌며 하나씩 더해나가는 방식이었다. 하지만 주어지는 표의 최대크기가 상당히 크며 반복횟수또한 10만회로, 시간초과가 발생한다.

따라서 이 문제는 dp 방식으로 해결하려했다.

• 먼저 테이블을 dp[i][j] : i,j구간의 합 으로 정의했다.

• 그렇다면 이 부분을 어떻게 구할 수 있을까?

• dp[2][4]를 구하기위해서는, 빨간색 부분과 파란색 부분을 합한부분에서, 중복되어 더해지는 노란부분을 빼준 뒤 (2,4)의 숫자를 더해주면 된다.

• 일반화를 하면, dp[i][j] = dp[i-1][j] + dp[i][j-1] - arr[i][j] 가 된다.

이제 두 좌표가 주어졌을 때 그 사이 구간의 합은 어떻게 구할까?

이 역시 똑같은 방법으로 구할 수 있다.

• 구하고자하는 부분은 주황색부분 (2,3) ~ (3,5) 구간의 합이다.

1. 파란색 큰 네모부분에서 빨간색 네모부분을 뺀다.
2. 파란색 큰 네모부분에서 분홍색 네모부분을 뺀다.
3. 중복되어 빠지는 노란색부분을 한 번 더해준다.

• 필요한 부분들을 식으로 표현해보자면 다음과같다.
  • 파란색 네모부분 : dp[3][5]
  • 빨간색 네모부분 : dp[1][5]
  • 분홍색 네모부분 : dp[3][2]
  • 노란색 네모부분 : dp[1][2]
• 따라서 구하고자하는 부분을 식으로 나타내면 answer = dp[3][5] - dp[1][5] - dp[3][2] + dp[1][2] 가 된다.
• 일반화를 해보면 answer = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] 이 된다.

#include <iostream>

using namespace std;

int dp[1025][1025];					// .. i,j 부분의 합


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

	int n, m;
	cin >> n >> m;

	int temp;

	// 표 입력 및 dp채우기
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= n;j++)
		{
			cin >> temp;
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + temp;
		}
	}

	// 답 구하기( (x1,y1) (x2,y2) 입력 => m번 반복 )
	for (int i = 1;i <= m;i++)
	{
		int x1, x2, y1, y2;
		cin >> x1 >> y1 >> x2 >> y2;

		int ans = 0;
		ans = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
		cout << ans << "\n";
	}
}