[DP, 2차원, 누적합, 파이썬] 백준 11660. 구간합구하기

2차원 DP를 푸는 게 아직 너무 어색하다,

• 어려웠던 점
  1. 누적합 데이터를 쌓아가는 부분
  2. 누적합 그래프를 바탕으로 일부 값을 계산하는 식을 짜는 부분

 

 

참고한 블로그

[python/파이썬] 백준 11660 구간 합 구하기 5

 

[백준] 11660 구간 합 구하기 5 (python) - 누적 합 (2차원) 정리

 

코드

import sys
input = sys.stdin.readline
#sys.stdin = open("input.txt", "rt")

N, M = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(N)]
DP = [[0] * (N + 1) for _ in range(N + 1)]


for i in range(1, N + 1):
    for j in range(1, N + 1):
        DP[i][j] = DP[i - 1][j] + DP[i][j - 1] - DP[i - 1][j - 1] + G[i - 1][j - 1]
        # point !!

for k in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    result = DP[x2][y2] - DP[x2][y1 - 1] - DP[x1 - 1][y2] + DP[x1 - 1][y1 - 1]
    # point !!
    
    print(result)