백준 11660 - 구간 합 구하기5 / 2차원 구간 합 알고리즘

 

www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

문제

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이다.

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

 

 

풀이

이 문제는 지난 번에 풀었던 백준 11659 - 구간 합 구하기 4를 응용하는 문제이다.

지난 문제가 1차원 배열 이었다면 이번 문제는 2차원 배열이라는것이 차이점이고, 접근 방법은 비슷하다.

 

아마 저번 문제처럼, 주어진 배열에서 처음부터 주어진 인덱스까지의 합 sums 배열을 만들어야만 할 것 같다.

 

만약 3x3 배열이라하면

1	2	3
4	5	6
7	8	9

1. 먼저 1차원 배열에서 처럼 오른쪽으로 합을 구하면 다음과 같은 배열을 얻을 수 있다.

1	1+2	1+2+3
4	4+5	4+5+6
7	7+8	7+8+9

2. 그 다음으로 이번에는 이 배열에서 아래방향으로 합을 구해준다.

1	1+2	1+2+3
1+4	1+2+4+5	1+2+3+4+5+6
1+4+7	1+2+4+5+7+8	1+2+3+4+5+6+7+8+9

 

그러면 (1,1)칸부터 (x,y)까지의 합은 (x,y) 좌표에서 구할 수 있다.

그 다음으로는 주어진 두 좌표에 따라서 그 좌표내에서의 값을 구하면 된다.

쉽게 생각하기 위해 시작은 (0,0) 이라 하자.

출처 : https://eeasyy.tistory.com/16

위 그림을 이용하여 설명하면, 우리가 구하고자하는 영역은 파란 영역인데

sums[n-1][m-1] - sums[n-1][b-1] - sums[a-1][m-1] 을 일단 계산해야한다.

하지만 이 계산을 하고나면 sums[a-1][b-1] 까지는 2번 빠져서 결과적으로 전체값에서 1번 빠지는 꼴이기 때문에, 한번 더해주어야 0으로 처리된다.

결론 : sums[n-1][m-1] - sums[n-1][b-1] - sums[a-1][m-1] + sums[a-1][b-1]

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = []

for _ in range(n):
    arr.append(list(map(int,input().split())))

sums = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    for j in range(n):
        if j == 0:
            sums[i][j] = arr[i][j]
        else:
            sums[i][j] = sums[i][j-1] + arr[i][j]

for i in range(n):
    for j in range(n):
        if i == 0:
            continue
        else:
            sums[i][j] += sums[i-1][j]

for _ in range(m):
    x1,y1,x2,y2 = map(int,input().split())
    x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
    if x1==0 and y1==0:
        print(sums[x2][y2])
    elif x1 == 0:
        print(sums[x2][y2] - sums[x2][y1-1])
    elif y1 == 0:
        print(sums[x2][y2] - sums[x1-1][y2])
    else:
        print(sums[x2][y2] - sums[x1-1][y2] - sums[x2][y1-1] + sums[x1-1][y1-1])