백준 11660 구간 합 구하기 5

풀이 과정

• 모든 2차원 배열의 값에 대해 0,0 부터 해당 위치까지 모든 수를 구한 값을 dp에 넣는다.
• 합을 구하려는 우측하단 위치의 값에서 좌측상단 위치의 값을 뺀다.
  • (x2,y2) - (x1,y2) - (x2,y1) + (x1,y1)
  • 이 때에 인덱스 값에 주의한다.
  • 제외하려는 사각형은 해당 꼭지점의 좌측 상단 대각선에 위치한 값이어야해서 x1, y1에 -1을 해줬다. 그러나 입력 좌표로 0이 들어온 경우가 있으므로 예외처리를 따로 했다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
map_lst = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
    for j in range(N):
        if j > 0:
            map_lst[i][j] += map_lst[i][j - 1]
for i in range(N):
    for j in range(N):
        if i > 0:
            map_lst[i][j] += map_lst[i - 1][j]
            
for _ in range(M):
    y1, x1, y2, x2 = map(int, input().split())
    x1 -= 2
    x2 -= 1
    y1 -= 2
    y2 -= 1
    if x1 == -1 and y1 == -1:
        print(map_lst[y2][x2])
    elif x1 == -1:
        print(map_lst[y2][x2] - map_lst[y1][x2])
    elif y1 == -1:
        print(map_lst[y2][x2] - map_lst[y2][x1])
    else:
        print(map_lst[y2][x2] - map_lst[y1][x2] - map_lst[y2][x1] + map_lst[y1][x1])