2차원 DP (#11660)

#11660 구간 합 구하기 5 https://www.acmicpc.net/problem/11660

 

 

역시 반복문으로 막 푸니까 시간초과가 난다.

 

과거에 DP를 풀었던 기억을 되내이며 고민했다.

2차원으로 DP를 진행하면 된다.

 

 

import sys

input = sys.stdin.readline
n, m = map(int, input().split())

maps = []
dp = []

# make dp and store origin
for i in range(n):
    nums = [int(x) for x in input().split()]
    # store origin
    maps.append(nums)

    # make dp
    tmp = []
    if i == 0:
        idx_0 = nums[0]
        tmp.append(idx_0)
    else:
        idx_0 = nums[0] + dp[i - 1][0]
        tmp.append(idx_0)
    for j in range(1, n):
        if i == 0:
            tmp.append(tmp[j - 1] + nums[j])
        else:
            tmp.append(tmp[j - 1] + dp[i - 1][j] + nums[j] - dp[i - 1][j - 1])
    dp.append(tmp)

# for t in maps:
#     print(t)
# print("")
# for t in dp:
#     print(t)

for _ in range(m):
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    # print(x1, y1, x2, y2)
    result = dp[x2][y2]
    if x1 - 1 >= 0:
        result -= dp[x1 - 1][y2]
    if y1 - 1 >= 0:
        result -= dp[x2][y1 - 1]
    if x1 - 1 >= 0 and y1 - 1 >= 0:
        result += dp[x1 - 1][y1 - 1]
    # print(dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1])
    print(result)

 

 

약간의 센스가 필요한 문제이기도 했다.