[백준 2167번] 2차원 배열의 합 - Python / 2차원 배열 누적합

문제 링크

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

2167번: 2차원 배열의 합

 

풀이 

기본적인 2차원 배열 누적합을 구하는 문제로, 알아두면 좋을 것 같다. 

2차원 배열의 누적합의 경우, 

dp[i][j] = 본래값 + 왼쪽 누적합 + 오른쪽 누적합 - 대각선 누적합 으로 구할 수 있다. 

특정 구간 (x1, y1) ~ (x2,y2) 까지의 누적합은 

dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] 로 구할 수 있다. 

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

graph = []

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

dp = [[0] * (m+1) for _ in range(n+1)]

# 누적합 구하기 
for i in range(1, n+1):
    for j in range(1, m+1):
        # 누적합 = 본래값 + 왼쪽 누적합 + 오른쪽 누적합 - 대각선 누적합 
        dp[i][j] = graph[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] 

k = int(input())

for _ in range(k):
    i, j, x, y = map(int,input().split())
    # 누적합 이용하여 결과 구하기 
    print(dp[x][y] - dp[i-1][y] - dp[x][j-1] + dp[i-1][j-1])