[Baekjoon 11660 / python / 실버1] 구간 합 구하기 5

문제

 

누적 합, DP 문제이다.

2차원 리스트를 사용하기 때문에 단일 리스트보단 조금 더 복잡하다.

 

# 실버1 -> 누적 합

"""

N : 표의 크기

M : 합을 구해야 하는 횟수

"""

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

origin = [list(map(int, input().split())) for _ in range(N)]

# dp(누적 합)테이블 생성

dp = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(1, N + 1):

    for j in range(1, N + 1):

        dp[i][j] = origin[i-1][j-1] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]

# 메인 로직

for i in range(M):

    x1, y1, x2, y2 = map(int, input().split())

   

    result = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

    print(result)

 

일단, dp 테이블은 직사각형 단위로 누적 합을 계산해야 한다. 왼쪽에서 오른쪽으로, 위에서 아래로 진행하며 누적 합을 구하는 게 아니라 x1 <= x2 and y1 <= y2 이므로 직사각형 모양으로 구해야 한다.

 

origin

dp 테이블 제작

 

dp 테이블은 모든 요소에 점화식을 적용시키기 위하여 0으로 패딩하여 제작한다.

하늘색으로 표시된 영역의 누적 합, 즉 검은 사각형으로 표기된 "15"라는 값을 구하고 싶다면,

빨간색으로 된 사각형 두개의 누적 합을 더한 후(8 + 6),

두 부분의 겹치는 부분의 크기인 3을 빼주고,

"15"와 같은 위치에 있는 origin 테이블의 4를 더해주면 된다.

 

정답 출력 로직

 

그렇게 만들어진 dp 테이블을 이용하여 정답을 M 번 출력하면 된다.

검은색으로 표시된 영역의 누적 합을 구하고 싶을 때, 64는 모든 영역을 더한 값이므로 검은 영역을 제외한 부분의 크기를 빼주면 된다.

즉 빨간색으로 표기된 부분의 누적 합 2개 (10, 10)을 64에서 빼 주고,

"1"은 빨간색 두 부분이 겹친 부분이라 두번 빠졌으므로 한번 더해주면 된다.

 

 

결과