[백준/다이나믹 프로그래밍 2] - 주지수

문제 링크

코드

# 영토 입력
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

# 직사각형 범위 입력
k = int(input())
ranges = [list(map(int, input().split())) for _ in range(k)]

# 누적합 배열 생성
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] = arr[i - 1][j - 1] + dp[i][j - 1]
        
# 열 누적합
for i in range(1, n + 1):
    for j in range(1, m + 1):
        dp[i][j] += dp[i - 1][j]

# 결과 확인
for x1, y1, x2, y2 in ranges:
    _sum = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]
    
    print(_sum)

풀이

일반적인 누적합 문제이다. 만약 단순 반복문을 사용한다면 시간초과가 발생한다. (시간복잡도 ➡️ 직사각형 범위의 개수 X 행의 크기 X 열의 크기 이기 때문)

누적합을 사용해서 미리 합을 구한 후, 각 사각형의 범위에 맞는 값을 그때 그때 출력해준다.

점화식은 아래와 같다.
dp[i][j] = 좌표 (i, j)까지의 누적합

누적합에 관한 설명은 다른 포스팅을 참고..