백준 11660 구간 합 구하기 5 Python

🐸 문제 정보

11660번: 구간 합 구하기 5

 

🤖 알고리즘

누적합

 

⏱️ 풀이 시간

13.22m

 

📝 풀이

그래프를 그려보고 누적합 테이블을 구하는 원리와, 답을 찾는 원리를 알아냈더니 쉽게 풀 수 있었다.

• 누적합 테이블 구하기
  • pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1]
• 구간 합 구하기
  • pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1]

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n, m = list(map(int, input().rstrip().split()))
pre = [[0] * (n + 1)] + [[0] + list(map(int, input().rstrip().split())) for _ in range(n)]

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

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