#374 백준 파이썬 [11660] 구간 합 구하기 5

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

 

SOLUTION

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

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

시간을 줄일 수 있는 방법은 2차원 배열을 얼마나 빠르게 채우냐에 따라 달려있다.

메인 식은 다음과 같다.

시작 좌표가 i, j 끝좌표가 x, y라고 가정할 때,

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) 예외 처리만 확실하게 해준다.

 

사실 각 열에 1,1부터 x,y까지의 sum을 저장할 필요도 없다.

각 행의 1열부터 n 열까지의 합만 저장해둔뒤,

y1~ y2까지의 값을 구하면 된다.

이건 아래 코드에 올려둔다.

PYTHON CODE

배열의 sum으로 구할 경우(pypy)

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

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


#i, j까지 sum한 매트릭스 따로 만들어주기 
sum_matrix = copy.deepcopy(matrix)
for i in range(N):
    for j in range(N):
        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] + sum(matrix[i][:j])


#예외 처리(i-2, j-2가 안되는 경우) 해주고 정답 출력
for _ in range(M):
    i, j, x, y = map(int, sys.stdin.readline().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])

 

각 열의 sum으로 구할 경우(pypy)

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

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

#열별로 sum한 매트릭스 따로 만들어주기 
for i in range(N):
    for j in range(N):
        if j == 0:
            pass
        else:
            matrix[i][j] += matrix[i][j-1] 

#행별 합 출력
for _ in range(M):
    i, j, x, y = map(int, sys.stdin.readline().split())
    answer = 0
    for k in range(i-1, x):
        if j != 1:
            answer -= matrix[k][j-2]
        answer += matrix[k][y-1]
    print(answer)