[백준] #11660 구간 합 구하기5 (python)

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

문제 설계

M값이 100,000이기 때문에 매번 순회하면 시간초과

DP이용

 

누적 합 공식

dp[i][j] =

dp[i-1][j] # 위쪽 누적

+ dp[i][j-1] # 왼쪽 누적

- dp[i-1][j-1] # 위+왼쪽 겹친 부분은 한 번 빼줌

+ arr[i-1][j-1] # 현재 셀 값

 

(주의: arr은 0-based)

 

문제 풀이

N,M=map(int,input().split())

number=[]
for _ in range(N):
    number.append(list(map(int,input().split())))


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][j-1]+dp[i-1][j]-dp[i-1][j-1]+number[i-1][j-1]


for _ in range(M):

    x1,y1,x2,y2=map(int,input().split())

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

정리

그림을 그리면서 풀어보면 더 쉽게 풀 수 있다.