문제 링크 -> https://www.acmicpc.net/problem/2167

---

1. 문제

2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.

입력
첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M).

출력
K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 231-1보다 작거나 같다.

---

2. 접근

첫 번째, 2차원 배열을 돌며 직접 합을 누적해 주는 방법으로 문제를 해결했다. 이중 for 문을 사용하는 코드라서 python 3으로 제출하면 시간 초과가 났고, pypy3으로 제출 성공하였다.

두 번째, python 3으로 해결할 수 있는 방법은 없을까 검색해 보니 대부분 동적계획법으로 풀이하고 있었다.
입력받은 N, M 크기의 배열 말고 같은 크기의 배열을 하나 더 만들어 (0, 0)부터 해당 인덱스까지의 합을 담아준다.
(x, y) 까지의 합을 구한 후 문제가 원하지 않는 (i, j) 이전의 값 (x, j-1) 과 (i-1, y) 을 제외시켜준다. 이 과정에서 중복 제거된 (i-1, j-1) 값을 다시 더해주면 DP점화식이 완성된다.

dp[x][y] = dp[x-1][y] + dp[x][y-1] - dp[x-1][y-1] + arr[x][y]

참고 : 백준 2167번 2차원 배열의 합 (Python, DP)
[백준] 2차원 배열의 합 - 2167번 문제 (Python)

---

3. 코드

• 이중 for문을 활용

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

k = int(input())
for _ in range(k):
    ans = 0
    i, j, x, y = map(int, input().split())
    for row in range(j-1,y):
        for col in range(i-1,x):
            ans += arr[col][row]
    print(ans)

• 다이나믹 프로그래밍 활용

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for i in range(m+1)] for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        dp[i][j] = arr[i-1][j-1] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]

k = int(input())
for _ in range(k):
    i, j, x, y = map(int, input().split())
    print(dp[x][y] - dp[x][j-1] - dp[i-1][y] + dp[i-1][j-1])

---

4. 추가

다이나믹 프로그래밍으로 풀 생각을 전혀 못했다.
누적 합을 더하는 문제는 다이나믹 프로그래밍을 고려해 보자.
점화식 세우는 연습도 더 필요하다.

---

알고리즘 분류

• 구현
• 누적 합