3-4. [구간합] 구간 합 구하기 2

구간 합 구하기 5

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

35640

16681

12960

46.003%

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 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 복사

4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

예제 출력 1 복사

27
6
64

예제 입력 2 복사

2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2

예제 출력 2 복사

1
2
3
4

 

---

풀이

 

1. 2차원 구간 합 배열 만들기

 

원본 (A)

	1	2	3	4
1	1	2	3	4
2	2	3	4	5
3	3	4	5	6
4	4	5	6	7

구간 합 배열(S)

S[i][j] = S[i - 1][j] + S[i][j - 1] - S[1][1] + A[i][j]

 

예시)

S[2][2] = S[1][2] + S[2][1] - S[1][1] + A[2][2] = 3 + 3 - 1 + 3 = 8

	1	2	3	4
1	1	3	6	10
2	3	8	15	24
3	6	15	27	42
4	10	24	42	64

 

(2, 2) ~ (3, 4)까지의 합을 구하려면?

(1, 1) ~ (3, 4)의 사이에서 X친 부분을 다 뺀다

그런데, (1, 1) 부분은 중복해서 2번 빼니, (1, 1)을 한 번 더한다.

	1	2	3	4
1	1(X)(X)	2(X)	3(X)	4(X)
2	2(X)	3(2, 2)	4	5
3	3(X)	4	5	6(3, 4)
4	4	5	6	7

 

따라서

정답은

42 - (10 + 6) + 1 = 27

	1	2	3	4
1	1	3	6	10(1~4)
2	3	8	15	24
3	6(1~3)	15	27	42
4	10	24	42	64

---

코드

const length = 4;
const A = [
  [1, 2, 3, 4],
  [2, 3, 4, 5],
  [3, 4, 5, 6],
  [4, 5, 6, 7],
];

const D = [
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0],
];

for (let i = 0; i < A.length; i++) {
  D[0][i] = D[0][i - 1 >= 0 ? i - 1 : 0] + A[0][i];
  // D[i][0] = D[i - 1 >= 0 ? i - 1 : 0][0] + A[i - 1 >= 0 ? i - 1 : 0][0];
}
for (let i = 1; i < A.length; i++) {
  // D[0][i] = D[0][i - 1 >= 0 ? i - 1 : 0] + A[0][i];
  D[i][0] = D[i - 1][0] + A[i][0];
}

for (let i = 1; i < length; i++) {
  for (let j = 1; j < length; j++) {
    D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j];
  }
}

const [x1, y1, x2, y2] = [2, 2, 3, 4];

const X1 = x1 - 1;
const Y1 = y1 - 1;
const X2 = x2 - 1;
const Y2 = y2 - 1;

const result = D[X2][Y2] - D[X1 - 1][Y2] - D[X2][Y1 - 1] + D[X1 - 1][Y1 - 1];

console.log(result);