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

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

 

 

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

 

풀이

처음에는 단순히 구간 합을 이용하여 행을 기준으로 값을 더한 배열을 만들어 해당 배열을 통해 범위 값을 구하려 했지만 시간초과로 문제를 풀지 못했다..

import sys
input=sys.stdin.readline


N,M=map(int,input().split())

array=[[0]*(N+1)]

sum_array=[[0]*(N+1) for _ in range(N+1)]

for i in range(N):
    row=[0]+[int(x) for x in input().split()]
    array.append(row)


for i in range(N):
    for j in range(N):
        sum_array[i+1][j+1]=sum_array[i+1][j]+array[i+1][j+1]
for i in range(M):
    result=0
    x1,y1,x2,y2=map(int,input().split())

    for i in range(x2-x1+1):
      result+=(sum_array[x1+i][y2]-sum_array[x1+i][y1-1])

    print(result)

 

 

 

어떻게 하면 ?
행과 열값을 모두 더한 구간 합 배열을 만들자 !
값을 채우는 구간 합 공식 : D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]
범위 값을 찾는 공식 : D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]

N=4 이고 x1,y2= 2,2 x2,y2=3,4 일 때 

 

다음과 같이 표가 있을 때 구간 합 표를 만들어보자

2차원 구간합 표를 만드는 방법은 

위의 공식대로 

 D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j] 의 방식을 취한다.

구하려는 D[i][j]를 기준으로 위의 값과 왼쪽 값을 더하고 중복되는 값을 뺀 값이라는 의미이다.

 

 

 

 

 

 

일단 행/열을 0기준이 아니라 1을 기준으로 하였고 초기값을 설정해주지 않을 것이니 0으로 위와 왼쪽을 감싸준다.

 

 

우선 42의 값은 파란색으로 그러진 공간의 총합이다.

그러면 초록색 선과 빨간색 선의 합을 빼고 겹쳐진 값을 빼면 파란색으로 칠해진 공간의 합을 알 수 있다.

 즉 42 - 10 - 6 + 1 = 27 인 것이다.

x1,y2= 2,2   x2,y2=3,4 이므로

42 = D[x2][y2] 

10 = D[x1-1][y2] 

6 = D[x2][y1-1]

1= D[x1-1][y1-1]

 

 

 

 

그리하여 범위 값을 찾는 공식은 :   D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1] 이다.

 

 

소스코드

import sys
input=sys.stdin.readline


N,M=map(int,input().split())

array=[[0]*(N+1)]

sum_array=[[0]*(N+1) for _ in range(N+1)]

for i in range(N):
    row=[0]+[int(x) for x in input().split()]
    array.append(row)

for i in range(1,N+1):
    for j in range(1,N+1):
        sum_array[i][j]=sum_array[i-1][j]+sum_array[i][j-1]+array[i][j]-sum_array[i-1][j-1]

for i in range(M):
    x1,y1,x2,y2=map(int,input().split())
    result=sum_array[x2][y2]-sum_array[x1-1][y2]-sum_array[x2][y1-1]+sum_array[x1-1][y1-1]

    print(result)