[#알고리즘/DP/[백준]11660번: 구간 합 구하기 5(python)]

Question

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

Solution

dp를 이용하였다. (1, 1)에서 각 인덱스까지의 구간 합을 구한 결과를 dp 배열에 저장한다. 그 후, dp 배열에 저장된 값을 이용하여 원하는 위치의 구간 합을 구한다.

Code

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

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


for i in range(n) :
    for j in range(n) :
        dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] + number[i][j] - dp[i][j]
        

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

후기

dp 배열에 저장할 구간 합을 구하는 부분에서 시간이 소요됐다. 겹치는 구간을 유의하자.