🟩 [백준] [Python] [구현] 2167번_2차원 배열의 합

문제

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

2167번: 2차원 배열의 합

풀이

# 백준 2167번 문제 - 2차원 배열의 합
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

k = int(input())
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] = arr[i-1][j-1] + dp[i][j-1] + dp[i-1][j]  - dp[i-1][j-1]

for _ in range(k):
    i,j,x,y = map(int, input().split())
    print(dp[x][y] - dp[x][j-1] - dp[i-1][y] + dp[i-1][j-1])

처음에 풀었을 때 시간초과가 발생하여서 DP를 사용하여 문제를 해결하였다.