[백준 파이썬 11660번]구간 합 구하기5★2차원 누적 합(prefix sum) 알고리즘★

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

VERSION 2.0

import sys

M = list(map(int , sys.stdin.readline().split(' ')))

A = [[0] * (M[0]+1)]
D = [[0] * (M[0]+1) for _ in range(M[0]+1)]

for i in range(M[0]):
    A_row = [0] + [int(x) for x in sys.stdin.readline().split()]
    A.append(A_row)

for i in range(1,M[0]+1):
    for j in range(1 , M[0]+1):

        D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]
print(D)
for _ in range(M[1]):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())

    result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]

    print(result)
#%%

※ 시간복잡도 오류

VERSION 1.0

import sys

M = list(map(int , sys.stdin.readline().split(' ')))

N = M[1]







prefix_2 = [ [0 for i in range(5)]]
for k in range(M[0]):
    a = 0
    prefix = [0]
    Nums = list(map(int , sys.stdin.readline().split(' ')))
    for i in range(M[0]):
        a += Nums[i]
        prefix.append(a)
    prefix_2.append(prefix)
# print(prefix_2)
# print(prefix_2[1][-1])
res = []
for i in range(N): #결과값 횟수
    RES = list(map(int , sys.stdin.readline().split(' ')))
    x_1 = RES[0]
    y_1 = RES[1]
    x_2 = RES[2]
    y_2 = RES[3]
    b = 0
    for k in range(x_1 , x_2+1):
        # print("prefix_2[{}][y_1] :{}".format(k, prefix_2[k][y_1]))
        # print("prefix_2[{}][y_2 - y_1] :{}".format(k , prefix_2[k][y_2 - y_1]))
        b += prefix_2[k][y_2] - prefix_2[k][y_1 - 1]

    print(b)


#%%