[백준] 구간 합 구하기 5

문제

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

---

풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
A = [[0]*(n+1)]
D = [[0]*(n+1) for _ in range(n+1)] # 합 배열

for _ in range(n):
    A_row = [0] + [int(x) for x in input().split()]
    A.append(A_row)

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

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

 

---

설명

- m의 크기가 큰 경우 (ex. 백준 11660 > 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000))
한번 정답판을 만들어 놓고, 질의가 오면 바로 답을 출력하는 형태