[CLASS 4]백준 11660번 - 구간 합 구하기 5

11660번 : 구간 합 구하기 5

 

연산을 딱 한번만 시킨다면 그냥 for문으로 돌아도 상관 없겠지만 연산 횟수 M이 많을 수 있기 때문에 시간을 단축하기 위해 DP로 짜야 한다.

 

그리고 이 문제는 좀 짜증나는게 dp테이블의 크기를 딱 n으로 만든다면 입력한 인덱스와 1차이가 나는 문제 때문에 머리가 아파진다.

 

그래서 dp테이블은 1 큰 크기로 만드는게 정신건강에 좋다.

 

내 코드:

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline

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

# dp테이블 구성
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] + mat[i-1][j-1]

# 출력
for _ in range(m):
    x1,y1,x2,y2 = map(int,input().split())

    print(dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1])

 

 

방법은 위 그림에서

 

(구하는 영역) = (전체 영역) - ( (영역2+영역3) + (영역1+영역3) - (영역3) )

-> dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1]

임을 이용하는 것이다.