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

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

 

풀이 이해

- (i, j) 부터 (x, y)까지 원소의 합을 구하는 문제인데, 순차 탐색으로 진행하면 시간이 오래 걸린다. 

- 빠르게 풀기 위해서는 2차원 행렬의 누적합을 이용해야하는데, 누적합 fast_sum을 만들어야 한다. 

- 이 때 fast_sum의 0행의 모든 열과 0열의 모든 행에 대해서는 별도의 연산을 진행해야하고, 그게 아닌 경우에는 일반식을 이용하면된다. 각 케이스에 대한 이해를 위해 그림을 이용했다. 

case 1. fast_sum[0][0] = matrix[0][0]

case 2. fast_sum[x][y] = matrix[x][y] + fast_sum[x][y - 1]

case 3. fast_sum[x][y] = matrix[x][y] + fast_sum[x - 1][y]

case 4. fast_sum[x][y] = matrix[x][y] + fast_sum[x - 1][y] + fast_sum[x][y - 1] - fast_sum[x - 1][y - 1]

- 이렇게 구한 fast_sum을 이용해서 (i, j) ~ (x, y) 원소의 합을 구한다. 이때도 각 케이스 별로 나누어서 진행해야한다. 

시작점인 (i, j) 값에 따라 나누어서 진행해야하는데,

i == 0 or j == 0인 경우는 위의 fast_sum을 구하는 것처럼 값을 구한 뒤 출력한다. 

i > 0 and j > 0인 경우에도 일반식으로 풀고 결과값을 출력하면 된다.

 

정답 풀이

i > 0 and j >0인 경우는 일반식으로 구했는데, 그 외의 엣지 케이스를 생각하지 못했다. 

문제를 풀 때 경계 부분 또는 엣지 케이스까지 생각하자!

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

matrix = []
for _ in range(n):
    matrix.append(list(map(int, input().split())))

# 누적합 계산 하는 2차 행렬  
fast_sum = [[0] * m for _ in range(n)]  
for x in range(n):
    for y in range(m):
        if x == 0 and y == 0:
            fast_sum[x][y] = matrix[x][y]
        elif x == 0 and y != 0:
            fast_sum[x][y] = matrix[x][y] + fast_sum[x][y - 1]
        elif x != 0 and y == 0:
            fast_sum[x][y] = matrix[x][y] + fast_sum[x - 1][y]
        else:
            fast_sum[x][y] = matrix[x][y] + fast_sum[x - 1][y] + fast_sum[x][y - 1] - fast_sum[x - 1][y - 1]        
        
k = int(input())
for _ in range(k):
    a, b, c, d = map(int, input().split())
    i, j, x, y = a - 1, b - 1, c - 1, d - 1 
    
    if i == 0 and j == 0:
        print(fast_sum[x][y])
    elif i == 0 and j != 0:
        print(fast_sum[x][y] - fast_sum[x][j - 1])
    elif i != 0 and j == 0:
        print(fast_sum[x][y] - fast_sum[i - 1][y])
    elif i != 0 and j != 0: 
        print(fast_sum[x][y] - fast_sum[x][j - 1] - fast_sum[i - 1][y] + fast_sum[i - 1][j - 1])