11660번 구간 합 구하기 5

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

아이디어

dp[i][j] = dp[i][j-1] + graph[i-1][j-1]

여기서 graph는 입력 받은 그대로의 2차원 리스트이고
dp 테이블은 0행과 0열은 0으로 가득 채운채, 각 행의 누적합이 저장되어 있는 테이블이다. 경험상 dp테이블은 0으로 채워진 행과 열이 있어야 계산하기 편한 것 같다.

ex)
graph
1 2
3 4

dp
0 0 0
0 1 3
0 3 7 이런 느낌이다.

---

x1, x2, y1, y2를 각각 비교해서 처리해주면 끝난다.

ex)
(2, 2) (3, 4)의 합을 구할 때
(2, 2) + (2, 3) + (2, 4) + (3, 2) + (3, 3) + (3, 4)
구하면 되므로 결국엔 dp[2][4] - dp[2][1] + dp[3][4] - dp[3][1]

코드

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

for i in range(n):
    graph.append(list(map(int, input().split())))

for i in range(1, n+1): # 누적합으로 dp 리스트 만듦
    for j in range(1,n+1):
        dp[i][j] = dp[i][j-1] + graph[i-1][j-1]

for i in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    answer = 0
    if x1 == x2 and y1 == y2:
        answer = graph[x1-1][y1-1]
    elif x1 == x2 and y1 != y2:
        answer = dp[x1][y2] - dp[x1][y1-1]
    else:
        for j in range(x1, x2+1):
            answer += dp[j][y2] - dp[j][y1-1]
    print(answer)