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

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

 

Solution

할 때마다 for 문을 행렬로 두 번 돌려 sum을 구하는 방식은 시간 초과가 난다. O(n^2)이기 때문.

1행 1열부터 x행 y열까지의 sum을 한 번에 구해놓고 sum_matrix 리스트에 저장한 뒤 더하기와 빼기로 구하는 방법을 활용한다.

메인 식은 다음과 같다.

print(sum_matrix[x-1][y-1] - sum_matrix[i-2][y-1] - sum_matrix[x-1][j-2] + sum_matrix[i-2][j-2])                                             

 

if문으로 리스트 범위를 벗어날 경우(i-2, j-2) 예외 처리만 확실하게 해준다.

 

Python Code

import copy
N, M = map(int, input().split())

#원래 매트릭스 받기
matrix = []
for _ in range(N):
    matrix.append(list(map(int, input().split())))

#i, j까지 sum한 매트릭스 따로 만들어주기 
sum_matrix = copy.deepcopy(matrix)
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            pass
        elif i == 0:
            sum_matrix[0][j] += sum_matrix[0][j-1]  
        elif j == 0:
            sum_matrix[i][0] += sum_matrix[i-1][0]
        else:
            sum_matrix[i][j] += sum_matrix[i-1][j]
            for col in range(j):
                sum_matrix[i][j] += matrix[i][col]

K = int(input())

#예외 처리(i-2, j-2가 안되는 경우) 해주고 정답 출력
for _ in range(K):
    i, j, x, y = map(int, input().split())

    if i == 1 and j == 1:
        print(sum_matrix[x-1][y-1])
    elif i == 1:
        print(sum_matrix[x-1][y-1] - sum_matrix[x-1][j-2])
    elif j == 1:
        print(sum_matrix[x-1][y-1] - sum_matrix[i-2][y-1])
    else:
        print(sum_matrix[x-1][y-1] - sum_matrix[i-2][y-1] - sum_matrix[x-1][j-2] + sum_matrix[i-2][j-2])