[BOJ/Python] 구간 합 구하기 5 || 다이나믹 프로그래밍

백준 구간 합 구하기 5 11660

11660번: 구간 합 구하기 5

❏ 문제 설명

❍ 문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

❍ 입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

❍ 출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

 

❏ 문제 풀이

❍ 풀이

1	2	3
2	3	4
3	4	5

dp[i][j]는 i와 j까지의 모든 누적합을 의미한다. 위의 예시를 표로 표현하면 다음과 같다.

1	1 + 2	1 + 2 + 3
1 + 2	1 + 2 + 2 + 3	1 + 2 + 3 +2 + 3 + 4
1 + 2 + 3	1 + 2 + 2 + 3 + 3 + 4	1 + 2 + 3 + 2 + 3 + 4 + 3 + 4 + 5

 

위의 표처럼 (i, j)까지의 모든 누적합을 구하기 위해선 필요한 부분은 더하고, 중첩된 부분은 제거하면 된다.
그림과 함께 살펴보자면, (3, 2)까지의 모든 누적합을 구하고자 한다.
따라서 하늘 색으로 이루어진 칸의 누적 합과, 파랑 색으로 이루어진 칸의 누적 합을 합한 후, 중첩된 그라데이션이 되어 있는 칸의 합을 빼면 된다. 그 후 (i, j) 칸의 수를 합한다.
코드로 살펴보면 다음과 같다.

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

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

이렇게 구해진 dp 2차원 리스트를 이용하여, (x1, y1)부터 (x2, y2)까지의 누적합을 구할 수 있다.
 

예를 들어 (2, 2)부터 (3, 3)까지의 누적합을 구하고 싶다면, dp[3][3]을 나타내는 빨간박스에서
dp[1][3]을 의미하는 파란 박스와 dp[3][1]을 의미하는 하늘색 박스를 뺀다.
그 후 중첩으로 제거된 곳을 의미하는 그라데이션으로 색칠된 부분을 다시 더해준다.
 

❍ CODE

import sys

input = sys.stdin.readline

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

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

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