[백준] 11660번 구간 합 구하기 5 (Python)

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

11660번: 구간 합 구하기 5

 

누적합은 익숙하지 않아서 항상 오래 걸린다.

이 문제는 DP까지 적용해야 했기 때문에 더 오래 걸렸다.

 

문제를 봤을 때 풀어야할 방법이 바로 생각 나서 구현했지만..

코드만 봐도 시간 초과가 무조건 날 것 같았다. 그리고 당연히 시간 초과가 났다.

 

시간 초과 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
board = []

for _ in range(n):
    board.append(list(map(int, input().split())))

for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    sum = 0

    for x in range(x1-1, x2):
        for y in range(y1-1, y2):
            sum += board[x][y]

    print(sum)

 

시간 초과를 해결하기 위해 누적합을 적용하고 DP를 적용했다.

그림으로 이해하면 어렵지 않다.

 

기존 숫자 표와 누적합 표이다.

 

배열이 1, 1부터 시작하며, dp가 누적합이라고 가정했을 때,

answer = dp[4][3] - dp[4][0] - dp[0][3] + dp[1][1]

 

배열이 1, 1부터 시작하며, dp가 누적합이라고 가정했을 때,

answer = dp[4][3] - dp[4][1] - dp[1][3] + dp[2][1]

 

이를 점화식으로 정리하면

answer = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

 

정답 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
board = []

for _ in range(n):
    board.append(list(map(int, input().split())))

dp = [[0]*(n+1) for i in range(n+1)]

for x in range(1, n+1):
    for y in range(1, n+1):
        dp[x][y] = dp[x][y-1] + dp[x-1][y] - dp[x-1][y-1] + board[x-1][y-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])