백준 2167 2차원 배열의 합

과정

• 누적 합 문제다.
• 2차원 배열을 입력 받고, 0,0 위치부터 해당 위치까지의 합을 저장해놓는다.
• 우측 하단까지의 합 - 좌측 상단까지의 합이 두 위치 사이 값의 합이 된다.

import sys

N, M = map(int, input().split())
map_lst = [list(map(int, input().split())) for _ in range(N)]

dx = [0, -1, -1]
dy = [-1, 0, -1]

for j in range(N):
    for i in range(M):
        for idx in range(3):
            ni = i + dx[idx]
            nj = j + dy[idx]
            if 0 <= ni < M and 0 <= nj < N:
                if idx == 2:
                    map_lst[j][i] -= map_lst[nj][ni]
                else:
                    map_lst[j][i] += map_lst[nj][ni]

K = int(input())

for _ in range(K):
    i, j, x, y = map(int, input().split())
    i -= 1
    j -= 1
    x -= 1
    y -= 1
    if i-1 < 0 and j-1 < 0:
        ans = map_lst[x][y]
    elif i-1 < 0:
        ans = map_lst[x][y] - map_lst[x][j-1]
    elif j-1 < 0:
        ans = map_lst[x][y] - map_lst[i-1][y]
    else:
        ans = map_lst[x][y] - map_lst[i - 1][y] - map_lst[x][j - 1] + map_lst[i - 1][j - 1]

    print(ans)