백준 2167번: 2차원 배열의 합

[문제 링크]

2167번: 2차원 배열의 합

---

필자는 1행 1열에서 1행 M열까지 숫자를 입력받는다고 했을 때, 1행 i열에 1열부터 i열까지의 합을 메모이제이션하였다.

미리 배열의 합을 계산한 이유는 1행 i열부터 1행 j열까지 배열의 합을 memo[1][j] - memo[1][i-1] 식으로 간단히 구할 수 있기 때문이다.

 

위 식을 이용하여 각 행마다 배열의 합을 구하고 결과값에 누적시켜주면 원하는 결과를 얻을 수 있다.

---

#include <iostream>
using namespace std;

int memo[301][301];

int Solution(int i, int j, int x, int y)
{
	int ret = 0;
	for (int col = i; col <= x; col++)
		ret += memo[col][y] - memo[col][j-1];

	return ret;
}

int main(void)
{
	int N, M;
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
	{
		int num, sum = 0;
		for (int j = 1; j <= M; j++)
		{
			cin >> num;
			sum += num;
			memo[i][j] = sum;
		}
	}

	int K;
	cin >> K;
	while (K--)
	{
		int i, j, x, y;
		cin >> i >> j >> x >> y;
		cout << Solution(i, j, x, y) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 82 day