[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])

---