[BOJ] 11660. 구간 합 구하기5(python)

📌문제

💪아이디어

1. (0,0)~(i,j)누적합 구하기
   
   • 해당 인덱스의 윗쪽 값은 (0,0)~(i-1,j)까지의 누적값이다.
     
   • 해당 인덱스의 왼쪽 값은 (0,0)~(i,j-1)까지의 누적값이다.
     
   • 윗쪽 누적값과 왼쪽값을 더하면 (0,0)~(i-1,j-1)누적값이 두 번 더해지기 때문에 한 번 빼줘야한다.
     

\[누적합[i][j]\ = \ 누적합[i-1][j] \ + \ 누적합[i][j-1] \ - \ 누적합[i-1][j-1]\]

1. (x1,y1) ~ (x2,y2) 범위의 누적합 구하기
   1번에서 한 과정과 반대로 생각하면 된다. 누적합[x2][y2]은 (0,0)~(x2,y2)의 누적합이다. (x1,y1)부터값을 구하기 위해서는 끝구간의 좌표를 기준으로 범위밖 첫번째 y축 평행 누적합과 범위밖 첫번째 x축 평행 누적합을 빼주고 시작구간의 대각선 누적합을 더해준다.
   

\[범위누적합\ = \ 누적합[x2][y2] \ - \ 누적합[x2][y1-1] \ - \ 누적합[x1-1][y2] \ + \ 누적합[x1-1][y1-1]\]

🥂코드

import sys; input = sys.stdin.readline
n, m = map(int,input().split())
arr = [[0 for _ in range(n+1)]for _ in range(n+1)]
for i in range(1,n+1):
    arr[i][1:] = list(map(int,input().split()))

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

for _ in range(m):
    x1, y1, x2, y2 = map(int,input().split())
    result = arr[x2][y2] - arr[x2][y1-1] - arr[x1-1][y2] + arr[x1-1][y1-1]
    print(result)