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

구간 합 구하기 5

🔍 알고리즘 분류

• 누적합

💡 문제 풀이

2차원 누적합 문제

1. arr와 누적합인 prefix_sum 2차원 배열의 첫 행, 첫 열을 모두 0으로 패딩을 넣어주는 것이 중요❗️
2. 누적합 생성 점화식
   • prefix_sum[i][j] = arr[i][j] + prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1]
3. 구간별(x1, y1, x2, y2) 합 구하는 점화식
   • sum = prefix_sum[x2][y2] - prefix_sum[x1-1][y2] - prefix_sum[x2][y1-1] + prefix_sum[x1-1][y1-1]

📄 코드

• Python

n, m = map(int, input().split())
arr = [[0] * (n + 1)] # 첫 행, 첫 열을 모두 0으로 채우고 시작
for _ in range(n):
    arr.append([0] + list(map(int, input().split())))

rectangles = []
for _ in range(m):
    a, b, c, d = map(int, input().split())
    rectangles.append((a, b, c, d))

# 누적합 생성: 역시 첫 행, 첫 열은 모두 0으로
prefix_sum = [[0] * (n + 1) for _ in range(n + 1)]

# 가로 쭉 채우기
sum = 0
for i in range(1, n + 1):
    sum += arr[i][1]
    prefix_sum[i][1] = sum
    
# 세로 쭉 채우기
sum = 0
for j in range(1, n + 1):
    sum += arr[1][j]
    prefix_sum[1][j] = sum

# 누적합 생성
for i in range(1, n + 1):
    for j in range(1, n + 1):
        prefix_sum[i][j] = arr[i][j] + prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1]        

# 구간별 누적합 구하기
for x1, y1, x2, y2 in rectangles:
    ans = prefix_sum[x2][y2] - prefix_sum[x1-1][y2] - prefix_sum[x2][y1 - 1] + prefix_sum[x1 - 1][y1 - 1]
    print(ans)