백준 11660: 구간 합 구하기 5

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

입출력 분석

• N * N 크기의 표가 주어지고, (x1, y1)부터 (x2, y2)까지의 합을 구한다.
• 합을 구하는 횟수가 최대 100,000이므로, O(N^2)는 불가함

알고리즘 분석

• 그리디 방식으로 해결할 경우 수행 시간은 O(N^2)가 소요되므로 불가
• dp로 누적합을 구하는 방법으로 해결

---

핵심 아이디어

(x1, y1)에서 (x2, y2) 사이의 합을 구하는 방법은 다음과 같다.

• (0, 0)부터 (x2, y2)까지의 합을 가져온다.
• (x2, y1)까지의 합(p1 + p2)을 뺀다.
• (x1, y2)까지의 합(p1 + p3)을 뺀다
• (x1, y1)까지의 합(p1)을 더한다.

이를 유도하기 위해서는 dp를 사용해 입력받은 표의 누적합을 계산해야 한다. 방법은 동일하지만 점화식은 약간 다르며, 아래 코드와 같다.

---

풀이

import sys  
  
input = sys.stdin.readline  
  
n, m = map(int, input().split())  
  
arr = []  
for _ in range(n):  
    arr.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 - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i - 1][j - 1]  
  
for _ in range(m):  
    x1, y1, x2, y2 = map(int, input().split())  
    result = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]  
    print(result)

주의 : (x1, y1) 값을 그대로 빼면 구하려는 영역까지 침범하므로, -1을 해줘야 한다!

---

결과