https://www.acmicpc.net/problem/15724
시간 2초, 메모리 512MB
input :
- N, M(1 ≤ N, M ≤ 1,024)
- N개의 줄에는 M개의 정수로 단위 구역 내에 살고 있는 사람 수
- K(1 ≤ K ≤ 100,000)
- x1, y1, x2, y2(x1 ≤ x2, y1 ≤ y2).
output :
- 직사각형 범위 내에 살고 있는 사람 수의 합을 출력
자주 봤던 2차원 부분 누적합을 계산하는 문제이다.
BOJ 20002 사과나무
동일한 알고리즘을 사용하는 문제로 많은 문제가 존재한다.
다른 부분이 없다.. 그냥 2차원 배열을 잘 생각해서 인덱스를 움직여야 한다.
2차원 부분 합 구하기
이 슬라이드를 보는 것이 좋은 방법일 수도 있다.
주의 할 점 하나는 입력 받는 인덱스는 1에서 시작하니 이 부분을 자신의 dp 배열과 비교해야 한다.
import sys
n, m = map(int, sys.stdin.readline().split())
graph, dp = [], [[0] * (m + 1) for _ in range(n + 1)]
for _ in range(n):
temp = list(map(int, sys.stdin.readline().split()))
graph.append(temp)
for x in range(1, n + 1):
for y in range(1, m + 1):
dp[x][y] = dp[x - 1][y] + dp[x][y - 1] - dp[x - 1][y - 1] + graph[x - 1][y - 1]
k = int(sys.stdin.readline())
for i in range(k):
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
print(dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1])
