백준 알고리즘 11660번 구간 합 구하기 5(python)

누적 합 & 다이나믹 프로그래밍 문제이다. 처음에는 아래 코드와 같이 풀었다. PyPy3로 제출해야 통과가 된다.

import sys

N, M = map(int, sys.stdin.readline().split())
li = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
for i in range(N):
    for j in range(1, N):
        li[i][j] = li[i][j-1]+li[i][j]
for _ in range(M):
    sy, sx, ey, ex = map(int, sys.stdin.readline().split())
    res = 0
    for i in range(sy-1, ey):
        if sx < ex:
            res += (li[i][ex-1]-li[i][sx-2]) if sx > 1 else li[i][ex-1] 
        else:
            res += li[i][sx-1]-li[i][sx-2] if sx > 1 else li[i][sx-1]
    print(res)

그러다 더 좋은 해답이 없나 찾아보다가 아래 코드같이 더 효율적으로 풀 수 있었다. 

import sys

N, M = map(int, sys.stdin.readline().split())
li = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dp = [[0]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, N+1):
        dp[i][j] = li[i-1][j-1] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]
for _ in range(M):
    sy, sx, ey, ex = map(int, sys.stdin.readline().split())
    res = dp[ey][ex] - dp[sy-1][ex] - dp[ey][sx-1] + dp[sy-1][sx-1]
    print(res)

res = dp[ey][ex] - dp[sy-1][ex] - dp[ey][sx-1] + dp[sy-1][sx-1] 가 핵심이다. (sy, sx)~(ey, ex)까지의 합을

구하기 위해 (1, 1)~(ey, ex)까지의 합에서 (1, 1)~(sy-1, ex)까지의 합과 (1, 1)~(ey, sx-1)까지의 합을 빼주게 되는데

이때 (1, 1)~(sy-1, ey-1)까지의 합은 2번 빼게 돼서 결과에 한 번 더해줘야 한다.