문제 링크

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

접근법 및 사용 알고리즘

• 누적 합

코드

• 시간초과 코드

import sys

n, m = map(int, sys.stdin.readline().split())
arr = []

sum_arr = []

sum = 0

for i in range(n):
    num = list(map(int, sys.stdin.readline().split()))
    arr.append(num)

for i in range(m):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    for y in range(y1-1, y2):
        for x in range(x1-1, x2):
            sum += arr[x][y]
    sum_arr.append(sum)
    sum = 0

for i in range(len(sum_arr)):
    print(sum_arr[i])

• 성공 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

prefix = [[0] * (len(arr[0]) + 1) for _ in range(n + 1)] # 누적 합 배열 생성

for i in range(1, n + 1):
    for j in range(1, len(arr[0]) + 1):
        prefix[i][j] = arr[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]  # 누적 합 계산

sum_arr = []
for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    total_sum = (prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1])
    sum_arr.append(total_sum)

for result in sum_arr:
    print(result)

얻은 교훈

누적 합의 원리 이용하기

• 각 인덱스 별 누적합을 구해두고, 끝 인덱스에서 시작 인덱스를 빼면 그 사이 값의 누적합이 계산됨!