[알고리즘 코딩테스트](2)자료구조-2: 구간 합(2)

[문제 4] 구간 합 구하기 2 

N * N개의 수가 N * N 크기의 표에 채워져 있다. 표 안의 수 중에 (x1, y1)에서 (x2,y2)까지의 합을 구하려고 한다. x는 행, y는 열을 의미한다. 예를들어 N=4이고 표가 다음과 같이 채워져 있을 때를 살펴보자. (2,2)에서 (3,4)까지의 합을 구하면 3+4+5+4+5+6+=27이고, (4,4)에서 (4,4)까지의 합을 구하면 7이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때 이를 처리하는 프로그램을 작성하시오.

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

 

 

입력

1번째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다(1<=N<1024, 1<=M<=100,000), 2번째 줄부터는 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 4개의 정수 X1,Y1,X2,Y2가 주어지며, (X1,Y1)에서 (X2,Y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. 

 

예제 입력

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 

 

예제 출력

27

6

64

 

문제 풀이

D[X][Y]= 원본 배열의 (0,0)부터 (X,Y)까지의 사격형 영역 안에 있는 수의 합
D[i][j]=D[i]D[j-1]+D[i-1]D[j]-D[i-1]D[j-1]+A[i][j]
// D[i-1]D[j-1]가 행으로 한 번, 열로 한 번 총 두번 더해지기 때문에 한번 빼줘야 함

예를 들어 질의가 2 2 3 4 라면 (3,4) 구간 합에서 (1,4)구간 합, (3,1) 구간 합을 뺀 다음 중복하여 뺀 (1,1) 구간 합을 더해주면 됨

질의 x1,x2,y1,y2에 대한 답을 구간 합으로 구하는 방법
D[x2][y2]-D[x1-1]D[y2]-D[x2][y1-1]+D[x1-1][y1-1] 

 

 

코드 구현하기

import sys
input = sys.stdin.readline
n,m=map(int,input().split())

A=[[0]*(n+1)] #[[0,0,0,0,0]]
D=[[0]*(n+1) for _ in range(n+1)] #[[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]

for i in range(n):
    A_row =[0]+[int(x) for x in input().split()]
    A.append(A_row)
    
print(A) #[[0,0,0,0,0],[0,1,2,3,4],[0,2,3,4,5],[0,3,4,5,6],[0,4,5,6,7]]
    
for i in range(1,n+1):
    for j in range(1,n+1):
        D[i][j]=D[i][j-1]+D[i-1][j]-D[i-1][j-1]+A[i][j]
        
print(D) #[[0,0,0,0,0],[0,1,3,6,10],[0,3,8,15,24],[0,6,15,27,42],[0,10,24,42,64]]

for _in range(m):
    x1,y1,x2,y2 = map(int, input().split())
    result = D[x2][y2]-D[x1-1][y2]-D[x2][y1-1]+D[x1-1][y1-1]
    print(result)

 

파이썬으로 행렬(Matrix) 구현하기

 

row=3
col=5
A=[0]*row
B=[[0]*row]*col

print(A) #[0,0,0]
print(B) #[[0,0,0],[0,0,0],[0,0,0]]

print([0]+[1]) #[0,1]
print([3]+[4]+[5]) #[3,4,5]