백준 2167번 <2차원 배열의 합>

백준 알고리즘 2167번

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

2167번: 2차원 배열의 합

---

2167번

입력으로 첫 줄에 배열의 크기 N, M이 주어진다. 그 다음 N개의 줄이 들어오는데 각 줄은 M개의 숫자로 이루어져있다.

배열의 정보가 모두 들어오고 나면 부분 합을 구할 개수 K가 주어진다. 그 다음 K개의 줄이 들어오는데 각 줄은 부분 합을 구할 좌표 두개에 대한 정보로 이루어져 있다.

 

출력으로는 K개의 부분합을 구해서 출력하면 된다.

---

문제 해결

이 문제는 구간 합 구하기를 이용해 풀면 된다.

 

https://seunghee114-blog.tistory.com/202

구간 합 구하기

---

코드

N, M = map(int, input().split())
temp = [list(map(int, input().split())) for _ in range(N)]
arr =[[0 for _ in range(M)] for _ in range(N)]

for i in range(N):
    for j in range(M):
        arr[i][j] += temp[i][j]
        if i-1 >= 0:
            arr[i][j] += arr[i-1][j]
        if j-1 >= 0:
            arr[i][j] += arr[i][j-1]
        if i-1 >= 0 and j-1 >= 0:
            arr[i][j] -= arr[i-1][j-1]

def SUM(a, b, x, y, arr):
    sum = arr[x][y]
    if a-1 >= 0 and b-1 >= 0:
        sum += arr[a-1][b-1]
    if b-1 >= 0:
        sum -= arr[x][b-1]
    if a-1 >= 0:
        sum -= arr[a-1][y]
    return sum

case = int(input())
for _ in range(case):
    a, b, x, y = map(int, input().split())
    print(SUM(a-1, b-1, x-1, y-1, arr))

---

결과

---