[Baekjoon] 2167. 2차원 배열의 합 (DP)

# Problem

2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다. 입력 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i ≤ x, j ≤ y). 출력 K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 231-1보다 작거나 같다.

 

# My Answer

n,m = map(int,input().split())
l = [[0] for _ in range(n+1)]

for idx in range(n):
    l[idx+1].extend(list(map(int,input().split())))

k = int(input())
for _ in range(k): 
    i,j,x,y = map(int,input().split())
    s=0
    for p in range(i,x+1):   
        for q in range(j,y+1):
            s+=l[p][q]
    print(s)

python에서는 시간 초과 

pypy3로 성공

 

# Solution  - DP

n,m = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(n)]
DP = [[0 for i in range(m+1)] for _ in range(n+1)]

# DP[i][j] = (1,1)에서 (i,j)까지의 부분합
for i in range(1,n+1):
    for j in range(1,m+1):
        DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + A[i-1][j-1]
        
for _ in range(int(input())):
    i,j,x,y = map(int,input().split())
    print(DP[x][y] - DP[i-1][y] - DP[x][j-1] + DP[i-1][j-1])    

DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + A[i-1][j-1] 에서

A는 앞에 0 이 없기 때문에 인덱스를 각각 1씩 빼준 값을 더해준다.