개요

백준 11660번: 구간 합 구하기 5

• 입력
  첫째 줄에 표의 크기 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. 숫자가 최대 100만개에 횟수도 10만개라서 각 횟수마다 범위내에 있는
   수들 계산하려하면 최대 1000억개의 연산을 해야한다.

   따라서 구간합구하기 4문제와 마찬가지로 범위가 큰 관계로 합 배열을 따로 만들어서 구해놔야한다.

2. 입력값이 2차원 배열인 관계로 2차원 합배열 Sum[i][j]을
   만들었다. Sum[i][j]는 0부터 i-1, 0부터 j-1값을 모두 더한 값이다.

3. Sum[i+1][j+1]은 Sum[i+1][j]+Sum[i][j+1]-Sum[i][j]+inputArr[i][j]로 표현할 수 있다.
   Sum[i][j]를 빼주는 까닭은 Sum[i+1][j]+Sum[i][j+1]에서 Sum[i]만큼 중복된 부분을 더하기 때문이다.

코드

#include<iostream>

using namespace std;
int N = 0, M = 0;
int Sum[1026][1026];
int inputArr[1025][1025];

void Input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> inputArr[i][j];
			//(i,j까지의 합은 i,j-1까지의 합+ i-1,j까지의 합 -  중복된 부분 + i,j좌표의 값)
			Sum[i + 1][j + 1] = Sum[i + 1][j] + Sum[i][j + 1] - Sum[i][j] + inputArr[i][j];
		}
	}

	for (int i = 0; i < M; i++) {
		int x1=0, y1=0, x2=0, y2 = 0;
		cin >> x1 >> y1 >> x2 >> y2;
        //x2,y2까지의 합- x2,y1-1까지의합 - x1-1,y2까지의 합 + x1,y1까지의합(중복된 부분)
		cout<<Sum[x2+1][y2+1] - Sum[x2+1][y1]-Sum[x1][y2+1]+Sum[x1][y1] << '\n';
	}
}

int main() {
	//c랑 c++입출력 분리
	ios_base::sync_with_stdio(0);
	//입력 출력 연결 분리
	cin.tie(0);

	Input();
}

문풀후생

처음엔 sum배열의 정의를 i-1,j-1까지의 합을 저장이아니라 ,
i,j까지의 합으로 정의하고
Sum[i + 1][j + 1] = Sum[i+1][j] + Sum[i][j+1] - Sum[i][j] + inputArr[i+1][j+1];
이렇게 구현했더니 inputArr[i][j]의 값을 받아온 후에,
Sum[i+1][j+1]에 inputArr[i+1][j+1]값을 저장하게 되어서
둘이 분리해서 구현하였다.

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> inputArr[i][j];
		}
	}
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= N; j++) {
			Sum[i + 1][j + 1] = Sum[i+1][j] + Sum[i][j+1] - Sum[i][j] + inputArr[i+1][j+1];
		}
	}

그 후, 찾아보니 sum배열을 i-1,j-1까지의 원소들을 더한것으로 저장하게되면 입력값 받자마자 처리할수 있게되어서 다시 구현했다.