[백준] 11660번 : 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

dp 테이블을 i번째부터 j번째까지의 누적합을 구하는 테이블을 만든다.

해당 테이블을 초기화하고 x1,y1, x2,y2의 좌표값을 받아 해당 구간의 합을 구하는 공식을 생각하여 풀었습니다.

 

누적합은 점화식 dp[i][j] = dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] + table[i-1][j-1]

x1, y1, x2,y2가 주어졌을때 구간합 구하는 점화식 dp[x1][y1] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

 

해당 점화식들은 그림을 그려보면서 해보면 쉽게 도출 해 낼 수 있습니다.

N , M = map(int, input().split()) #표의 크기 N, 횟수 M

table = []
for _ in range(N): # 테이블 생성
    table.append(list(map(int, input().split())))
    
answer = []
for _ in range(M): # x,y 좌표
    x1, y1, x2, y2 = map(int, input().split())
    answer.append([x1, y1, x2, y2])
    
dp = [[0 for _ in range(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][j-1] + dp[i-1][j] - dp[i-1][j-1] + table[i-1][j-1]

def rangeSum(x1, y1, x2, y2):
    return dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

for x1,y1,x2,y2 in answer:
    print(rangeSum(x1,y1,x2,y2))