[Python][백준] 11660번 구간 합 구하기5

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

공부 날짜 : 2023.01.26
정답 참조 여부 : △

2차원 배열에서 특정 구간의 합을 구하는 문제이다.

---

스스로 문제를 풀어보면 좋았을텐데 누적합 알고리즘을 공부하다가 2차원 배열의 누적합 표현하는 방법까지 설명이 나와있어서 바로 풀렸던 문제이다.

구간합을 구하는 방법은 스스로 이해하고 떠올렸지만, 2차원 누적합까지 스스로 떠올렸으면 더 좋았다는 생각이 들었다.

소스코드

import sys
input = sys.stdin.readline
##########################################
n, m = map(int, input().split())

# 누적합이 저장될 배열
sum_data = [[0 for _ in range(n+1)] for _ in range(n+1)]
    
# 2차원 누적합 저장
for i in range(1, n+1):
    a = list(map(int, input().split()))
    sum_temp = 0
    for j in range(1, n+1):
        sum_temp += a[j-1]
        sum_data[i][j] = sum_data[i-1][j] + sum_temp
        
# 누적합 출력
for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    print(sum_data[x2][y2] - sum_data[x1 - 1][y2] - sum_data[x2][y1 - 1] + sum_data[x1 - 1][y1 - 1])