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

문제

구간 합 구하기 5

문제 해설

N <=1024, M <=100,000의 제한조건이기 때문에 완전탐색을 이용하면
M * N ^ 2의 시간복잡도를 가지므로 당연히 시간 초과가 납니다.

그래서 DP를 이용하여 풀어야 하는데, DP는 2차원 리스트를 이용합니다.
DP[i][j]에는 (0, 0)에서 시작하여 i,j까지의 합을 구하여 값을 넣습니다.

다음 그림과 같이 초록색 부분을 구해야 한다면, DP 테이블에서 노란 부분 2개를 빼주고, 빨간 부분은 공통부분이기 때문에 한번을 더해줘야 합니다.

풀이 코드

import sys

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

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


# dp 채우기
for i in range(1, n + 1):
    for j in range(1, n + 1):
        dp[i][j] = graph[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]

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