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

by

섹션 합계 첫 번째 게시물로 이동

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