Baekjoon/Python) 2167 2차원 배열의 합 - DP, 누적합

💭 나의 접근 방법

---

 

1	2	3	4
5	6	7	8
9	10	11	12

위와 같은 2차원 배열이 있을때 특정 2차원 배열의 합을 구하는 방법

 

6이 (x,y) 이고 12가 (i,j) 일때

(x,y)에서 (i,j)위치까지의 지정된 수들의 합 공식

12까지의 합: 1번

4까지의 합: 2번

9까지의 합: 3번

1까지의 합: 4번

$$ (1) - (2) - (3) + (4) $$

따라서 2차원 배열의 합을 구하는 DP 테이블을 만들어준다.

for i in range(1,N+1):
    for j in range(1,M+1):
        sum_arr[i][j] = arr[i-1][j-1] + sum_arr[i-1][j] + sum_arr[i][j-1] - sum_arr[i-1][j-1]

• 합 테이블을 구하는 방법

현재 값의 왼쪽까지의 합 + 현재까지의 위쪽까지의 합 - 중복 합 + 현재 값

따라서 합 테이블을 만들고 지정 구간까지의 합을 $O(1)$ 시간 안에 구할 수 있다.

 

💡 결과

---

 

import sys
input = sys.stdin.readline

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

for i in range(1,N+1):
    for j in range(1,M+1):
        sum_arr[i][j] = arr[i-1][j-1] + sum_arr[i-1][j] + sum_arr[i][j-1] - sum_arr[i-1][j-1]
T = int(input())    

for test_case in range(T):
    sum = 0
    i,j,x,y = map(int,input().split())
    sum = sum_arr[x][y] - sum_arr[x][j-1] - sum_arr[i-1][y] + sum_arr[i-1][j-1]
    print(sum)

 

 

💫 느낀점

---

누적합 +  DP 문제로 자주 접한 문제여서 쉽게 접근할 수 있었다. 

DP 테이블은 N+1, M+1로 설정해 인덱스 범위를 벗어나는것을 해결할 수 있다!

 

 

 

주소)

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