[백준 2167][Python] 2차원 배열의 합

문제 링크 https://www.acmicpc.net/problem/2167

처음에는 하나하나 모두 더하는 식으로 문제를 구현했다.. 당연히 시간초과가 나왔고 질문 게시판을 뒤적...

값을 하나하나 더하는 방법으로는 시간 초과가 생길 수 있습니다.
어떤 배열의 a의 a[i]에서 a[j]까지의 합은 a[0]에서 a[j]의 합에서 a[0]에서 a[i-1]까지의 합을 뺀 값과 같습니다.
이를 이용하여 값을 입력받음과 동시에 요소들의 합을 구해놓고, 어떤 요청에 대해서 단순히 두 요소의 차를 구하는 것만으로 답을 구할 수 있습니다. -sth3353

라는 글로 구원을 받았다...

풀이

n, m = map(int, input().split())
a = []
list_s = [[0]*(m + 1)for _ in range(n+1)]
for _ in range(n):
    a.append([*map(int, input().split())])

for i in range(1, n+1):
    for j in range(1, m+1):
        list_s[i][j] = a[i-1][j-1] + list_s[i][j - 1] + list_s[i - 1][j] - list_s[i - 1][j - 1]

for _ in range(int(input())):
    i, j, x, y = map(int, input().split())
    print(list_s[x][y] - list_s[x][j - 1] - list_s[i - 1][y] + list_s[i - 1][j - 1])