[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)수식을 그대로 코드로 옮겼다.
📌 총평
재미재미
