[백준] 11660(구간 합 구하기 5)

구간 합 첫 게시글로 이동하기 

11660

👻접근

질의 개수 (M) 이 최대 100,000 이기 때문에 질의마다 합을 구하면 시간 복잡도가 올라가므로 구간 합 배열을 이용해야함.

2차원 구간 합 배열 D[X][Y] 정의
D[X][Y] = 원본 배열의 (0,0) 부터 (X,Y) 까지의 사각형 영역 안에 있는 수의 합 

풀이

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

질의 X1,Y1, X2,Y2 에 대한 답을 구간 합으로 구하는 방법
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())

A = [[0] * (N+1)] # 2차원 원본 배열
D = [[0] * (N+1) for _ in range(N+1)] # 2차원 합 배열 

# 원본 배열 A 값 입력 
for i in range(1,N+1):
    A_row = [0] + [int(x) for x in input().split()] 
    A.append(A_row)

# 합 배열 D 값 입력
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]

# 구간 합 구하기 
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)

# 입출력으로 확인하기 
4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

        A               D
[0, 0, 0, 0, 0]  [0, 0, 0, 0, 0]
[0, 1, 2, 3, 4]  [0, 1, 3, 6, 10]
[0, 2, 3, 4, 5]  [0, 3, 8, 15, 24]
[0, 3, 4, 5, 6]  [0, 6, 15, 27, 42]
[0, 4, 5, 6, 7]  [0, 10, 24, 42, 64]

2 2 3 4
42 - 10 - 6 + 1 = 27

3 4 3 4
42 - 24 - 27 + 15 = 6

1 1 4 4
64 - 0 - 0 + 0 = 64