[백준/python] 2167번: 2차원 배열의 합

문제

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

2167번: 2차원 배열의 합

---

문제 요약

N × N 크기의 2차원 배열을 입력 받고, 위치 (i, j) 부터 (x, y) 까지 있는 수들의 합을 출력한다.

 

+ (i, j), (x, y)는 배열의 i(x)번째 행, j(y)번째 열을 의미한다. (1부터 시작)

---

코드

import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
arr = [list(map(int, input().rstrip().split()))  for _ in range(N)]
# N개의 행과 M개의 열을 갖는 배열

K = int(input())
# 합을 구할 부분의 개수

psum = [[0] * (M + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, M + 1):
        psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1] + arr[i-1][j-1]
        # <이전 행 누적합> + <이전 열 누적합> - <이전 행, 열 누적합> + <현재 인덱스 값>
        # <이전 행, 열 누적합>을 빼주는 이유는 <이전 행 누적합>과 <이전 열 누적합>을 더할 때 <이전 행, 열 누적합>이 두 번 더해지기 때문
print(*psum)

for _ in range(K):
    i, j, x, y = map(int, input().rstrip().split())
    print(psum[x][y] - psum[x][j-1] - psum[i-1][y] + psum[i-1][j-1])
    # 그림 참고

---

코드 설명

1. N개의 행과 M개의 열을 갖는 배열 arr에 대한 누적합 배열 psum을 생성한다.

 

+ psum은 N+1개의 행과 M+1개의 열을 갖는 배열이다. (초기 행과 열을 0으로 설정)

 

예) 배열 arr 

1	4	4	9
3	2	7	6
5	2	8	8

 

예) 배열 psum의 초기 상태

0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0

 

1-1. psum[i][j] (arr[i-1][j-1] 까지의 누적합)을 psum[i-1][j] (이전 행 누적합) + psum[i][j-1] (이전 열 누적합) - psum[i-1][j-1] (이전 행, 열 누적합) + arr[i-1][j-1] (현재 인덱스의 arr값)으로 설정한다.

 

+ psum[i-1][j-1]을 빼주는 이유는 psum[i-1][j], psum[i][j-1]을 더할 때, psum[i-1][j-1]이 두 번 더해지기 때문이다.

 

예) 배열 psum[i][j] 값을 할당한 상태

0	0	0	0	0
0	1	5	9	18
0	4	10	21	30
0	9	17	36	59

 

2. (i, j) 부터 (x, y) 범위에 있는 수들의 합을 구한다.

 

예) (2, 2) 부터 (3, 4) 범위 수 구하기

0	0	0	0	0
0	1	5	9	18
0	4	10(i, j)	21	30
0	9	17	36	59(x, y)

 

psum(x, y)에서

0	0	0	0	0
0	1	5	9	18
0	4	10	21	30
0	9	17	36	59

 

psum[x][j-1]을 빼주고

0	0	0	0	0
0	1	5	9	18

 

psum[i-1][y]를 빼주고

0	0
0	1
0	4
0	9

 

두 번 뺀  psum[i-1][j-1]을 다시 더해준다.

0	0
0	1