[python/백준] 15724: 주지수

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

 

전형적인 누적합 문제라 이게 왜 DP에 있지? 하는 고민이 들었습니다

찾아보니 이런 식의 누적합 풀이법도 사실 DP 테이블을 사용하고 채우므로, 넓은 의미에서 DP 풀이가 맞다고 하더라구요!

 

import sys
input = sys.stdin.readline 

def main(): 
    n,m = map(int,input().split())
    ground = []
    for _ in range(n):
        ground.append(list(map(int,input().split())))
    
    prefixSum = [[0 for i in range(m+1)] for j in range(n+1)]

    for i in range(1,n+1):
        for j in range(1,m+1):
            prefixSum[i][j] = ground[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]

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

if __name__ == "__main__":
    main()