[Python - Dynamic Programming] 11660 구간 합 구하기 5

📌 문제

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

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

1	2	3	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)까지 합을 구해 출력한다.

📌 문제 풀이

👨‍🏫 접근

구간 합은 대표적인 다이나믹 프로그래밍 알고리즘을 사용하여 합을 구하는 방법론이다.

 

3부터 10까지 더해야 한다고 할 때, 아직은 적은 수이기 때문에 구하기 힘들지 않을 것이다. 하지만 369~1234의 합을 구하라고 하면 한세월이 걸릴 것이다. 이를 위해서 1~1234의 합과 1~369의 합을 이용하는 것이다. 1~1234는 다시 표현하면 1~368 + 369~1234 이기 때문이다. 즉 우리가 1~369까지의 합을 알면 369~1234의 합을 구하는 것은 1~1234의 합에서 1~368의 합을 빼주는 것과 같다.

 

그래서 구간 합 알고리즘을 아래처럼 사용한다.

n = int(input()) # 총 배열의 길이
arr = list(map(int, input().split()))

d = [0] * (n + 1)

for i in range(1, n + 1):
    d[i] += d[i - 1]
    
start, end = map(int, input().split())
print(d[end] - d[start - 1])

직접 생각해보면 왜 start에서 -1 해준 것을 빼주어야 하는 지 알 수 있을 것이다.

 

이것을 2차원으로 확장시키면 또 다르게 풀이가 가능하다. 문제의 경우 2차원의 배열에서의 구간 합을 구하라고 제시한다.

여기서 이전 x의 구간합을 끌어와 사용하면 된다.

 

문제에서 주어진 예제 처럼 아래와 같은 표가 있다고 할 때,

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

각 행들을 개별적으로 처리하면 다음과 같이 처리할 수 있다.

1	3	6	10
2	5	9	14
3	7	12	18
4	9	15	22

이제 여기서 열방향으로도 연산해준다.

1	3	6	10
3	8	15	24
6	15	27	42
10	24	42	64

이제 여기서 구간합을 구하려면 어떻게 해야 할까? 정답은 앞선 구간 합 알고리즘과 유사하게 포함하지 않는 범위를 제외시켜준다. 예를 들어, (x1, y1) == (2, 3) / (x2, y2) == (3, 4) 인 경우 3 + 4 + 5 + 4 + 5 + 6으로 총 27이다.

 

여기서 x2, y2 좌표의 값은 42인데 이 의미는 1, 1부터 3, 4까지 모두 더한 것과 같다.

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

그렇기 때문에 두 가지 구간을 제외시켜야 한다. 첫 번째 구간은 (1, 1) ~ (1, 4) 이다.

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

두 번째 구간은 (1, 1) ~ (4, 1) 이다.

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

그런데 그렇게 두 개를 빼버리면 둘이 공통으로 갖는 1이라는 구간은 두 번 빼준 것이기 때문에 총 합계와 맞지 않다. 따라서 중복으로 빼준 부분은 다시 더해야 한다.

 

그래서 이것을 수식으로 표현하면 아래와 같다.

$$ANS = A_{x_2y_2} - A_{(x_2)(y_1-1)} - A_{(x_1-1)(y_2)} + A_{(x_1-1)(y_1-1)}$$

 

 

👨‍🏫 문제 풀이

📄 전체 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

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

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

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

📄 준비

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

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

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

구간 합을 구하는 두 가지 절차는 개별적으로 진행되어야 한다. 안 그러면 이전 값을 중복으로 더하는 꼴이기 때문에 값이 매우 커진다.

📄 풀이

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

수식을 그대로 코드로 옮겼다.

📌 총평

재미재미