[백준/2167/파이썬] 2차원 배열의 합

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

2167번: 2차원 배열의 합

Problem

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

조건

• 첫째 줄에 배열의 크기 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).

SOL

 

완전탐색

2중반복을 이용하면 O(KMN)이 나와서, TL이 떠버렸따..

import sys
input = sys.stdin.readline
N,M =map(int,input().split())
board = [list(map(int,input().split())) for _ in range(N)]
#print(board)
K = int(input().rstrip())


for i in range(K):
    a,b,x,y =map(int,input().split())
    ans=0
    for start in range(a-1,x):
        for end in range(b-1,y):
            #print("board[start][end]",board[start][end])
            ans+=board[start][end]
    print(ans)

누적합 이용하기 (DP)

• 1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M이 조건 때문에, 누적합이 가능하다. 
• 예를들어, (1,3) ~ (2,2)까지의 합은, j<=y이므로 불가능하게 된다. 즉, 2차원 배열에서 직사각형이 아닌 모양은 나오지 않는다는 이야기!

누적합은 생각보다 쉽지않은 개념인데, 그림으로 그리는게 제일 시각적으로 잘보이고, 확 와닿는다.

DP[2][2]를 생각해보자

우선, 1차원 배열일 때 , 누적합은 그냥 말그대로 쭉 더해주면 된다. 

DP를 이용하면, DP[i-1] +arr[i] 일거고, 반복문을 이용하면, 변수 1개에다가 배열 값을 계속 누적시키는 방법이 있을거다.

그렇다면, 2차원 배열일 때, 누적합은 어떻게 구할까? 예시로 DP[2][2]를 생각해보자. 

 

DP[2][2] = arr(1,1 ~ 2,2)까지의 합이다. 

• 사람의 힘으로 구해보자. 1+2+10+8 = 21 이다.
• 근데, 우리는 사실 사람의 힘으로 구하는 과정은 2중반복을 쓰는거니까, 옆의 누적합의 표를 이용해서 구한다고 생각해보자.

• DP[1][2] = arr[1][1] +arr[1][2]
• DP[2][1] = arr[1][1] +arr[2][1]

즉, DP[2][2] = arr[1][1] +arr[1][2] +arr[2][1] +arr[2][2].

그림으로 봐도, 식으로 봐도 반복되는 부분이 보이게된다!

확실하게 하기위해서 한가지 더 예시를 들어보자, DP[3][3]은 어떻게 될까?

DP[3][3]

이제 좀 규칙성이 보이는가? arr[1][1]값이 반복되는게 아니라, 사실 arr[i-1][j-1] 까지의 누적합이 반복되는거다.

즉, DP table에 관한 식으로 나타내면,

• DP[i][j] = DP[i-1][j] +DP[i][j-1] -DP[i-1][j-1] +arr[i][j] 

코드로 구현할 때는, 위의 규칙을 깨지않게 하기위해, DP[0][~] ,DP[~][0] 에는 모두 0을 넣어줬다.

 

우리는 이제 누적합의 Dp table을 안다. 이제 i,j ~ x,y 까지의 누적합은 어떻게 구할까?

• 우리가 (1,3 ~2,6)까지의 누적합을 구한다고 생각하면, (1,1) ~(2,6) 의 누적합 - (2,2) 의 누적합을 하면 된다

2

그렇다면, 아래와 같은 곳을 구할때는 어떻게 될까?

DP[4][5] - (DP[4][2] +DP[2][5]) + DP[2][2] 가된다!

 

정리하자면, 누적합을 구하는 table을 구하고, 누적합을 이용해서 (i,j) ~(x,y)까지의 누적합을 쉽게 구할 수 있게된다.

import sys
input = sys.stdin.readline
N,M =map(int,input().split())
board = [list(map(int,input().split())) for _ in range(N)]
#print(board)
DP = [[0]*(M+1) for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(1,M+1):
        DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + board[i-1][j-1]

K = int(input().rstrip())
for _ in range(K):
    a,b,x,y = map(int,input().split())
    print(DP[x][y]-(DP[x][b-1]+DP[a-1][y])+DP[a-1][b-1])