206. 구간합 구하기 5

백준

1. 다이나믹 프로그래밍

참고

전체 합 행렬

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

#원래 매트릭스 받기
matrix = [list(map(int, input().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, 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])

행별 합

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

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

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, input().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)