[Python] 11660 구간 합 구하기

👉 11660 구간 합 구하기

[정답 코드]

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
matrix = []
memo = [[0] * n for _ in range(n)]
# making matrix and memo
for i in range(n):
    matrix.append(list(map(int, input().split())))
    memo[i][0] = matrix[i][0]
    for j in range(1, n):
        memo[i][j] = memo[i][j - 1] + matrix[i][j]
    if i != 0:
        for j in range(n):
            memo[i][j] += memo[i - 1][j]
            
# input x1, y1, x2, y2
for i in range(m):
    res = 0
    x1, y1, x2, y2 = map(int, input().split())
    res += memo[x2 - 1][y2 - 1]
    if y1 >= 2:
        res -= memo[x2 - 1][y1 - 2]
    if x1 >= 2:
        res -= memo[x1 - 2][y2 - 1]
    if x1 >= 2 and y1 >= 2:
        res += memo[x1 - 2][y1 - 2]
    print(res)

[풀이]

• matrix를 한 행씩 input 받음과 동시에 누적합을 memo에 저장한다. (여기서 누적합은 0행 0열부터 n행 m열 까지의 합을 의미한다.)
• x1행 y1열 부터 x2행 y2열까지의 구간 합 = (x2, y2)까지의 누적합 - (x2, y1)까지의 누적합 - (x1, y2)까지의 누적합 + (x1, y1)까지의 누적합

[오류 해결]
python list의 index에 음수가 들어가면 뒤에서부터 indexing하여 접근하기 때문에 조심해야한다. 이를 방지하기 위해 if y1 >= 2 등의 조건을 달아주었다.

[적용 자료구조 및 알고리즘]

• Dynamic Programming (Prefix Sum)