BOJ-11660-구간 합 구하기 5

[changicho]

11660. 구간 합 구하기 5

링크

난이도	정답률(_%)
Silver I	58.614

설계

메모이제이션

memo[y][x] 는 (0,0)~(y,x)까지의 합을 나타낸다.

정리

내 코드 (ms)	빠른 코드 (ms)
132

고생한 점

문제에서 주어지는 x와 y의 순서가 일반적으로 생각하는 arr의 y,x와 반대이다

코드

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

using namespace std;

int arr[1026][1026];
int memo[1026][1026];

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

	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= N; x++) {
			cin >> arr[y][x];

			memo[y][x] = arr[y][x] + memo[y][x - 1] + memo[y - 1][x] - memo[y-1][x-1];
		}
	}

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

		int answer = memo[x2][y2] - memo[x1 - 1][y2] - memo[x2][y1 - 1] + memo[x1 - 1][y1 - 1];

		cout << answer << "\n";
	}
}

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

	solution();

	return 0;
}