[BOJ: 15724] - Python / 파이썬 - 이건 꼭 풀어야해!

문제

• https://www.acmicpc.net/problem/15724

시간 복잡도

• n * m만큼 반복 + k만큼 반복 -> $O(nm + k)$
• n, m의 최대값은 1024, k는 10만이기 때문에 충분하다.

문제 접근법

• 접근 방법이 안떠올라서 구글링 -> 참조1, 참조2
• 푸는 방법 자체는 2차원 배열의 구간합이다.

1. 2차원 배열의 누적합을 구하기 위해선, 다음과 같은 공식을 통해 각 열마다 누적합을 구해준다.
   $dp[i][j] = area[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]$
2. k만큼 반복하며 좌표 입력을 받는다.
3. 2차원 배열의 구간합을 구하기 위해선, 다음과 같은 공식을 통해 원하는 구간의 합을 구해준다.
   $dp[i][j] - dp[x-1][j] - dp[i][y-1] + dp[x-1][y-1]$

코드

# BOJ
# S1 - 15724(주지수)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
people = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, m + 1):
        dp[i][j] = people[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]

for _ in range(int(input())):
    x1, y1, x2, y2 = map(int, input().split())
    print(dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1])