[백준] 11660 - 구간 합 구하기 5 (DP)

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

11660번: 구간 합 구하기 5

import sys
input = sys.stdin.readline
 
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * n for _ in range(n)]
dp[0][0] = graph[0][0]
for i in range(1, n):
    dp[i][0] = graph[i][0] + dp[i - 1][0]
    dp[0][i] = graph[0][i] + dp[0][i - 1]
 
for i in range(1, n):
    for j in range(1, n):
        dp[i][j] = graph[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
 
for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    dup = dp[x1 - 2][y1 - 2]
    if x1 - 2 >= 0:
        upper = dp[x1 - 2][y2 - 1]
    else:
        upper = 0
        dup = 0
    if y1 - 2 >= 0:
        left = dp[x2 - 1][y1 - 2]
    else:
        left = 0
        dup = 0
    print(dp[x2 - 1][y2 - 1] - upper - left + dup)

그냥 들어오는대로 누적 합 구하면 터진다.

DP를 이용해야 하는데, dp[i][j]는 dp[0][0]부터 dp[i][j]까지의 누적 합이다.

중간의 특정 사각형의 누적합을 구하려면, 그 사각형의 우측 하단의 누적 합에서 위쪽 누적합을 빼고, 왼쪽 누적합을 빼고, 중복돼서 2번 빼진 부분의 누적합을 더하면 된다.

 

그리고, 파이썬은 표준입력으로 하면 터지니 sys.stdin.readline 사용해야 한다.