[Python] BOJ / 11660번 / 구간 합 구하기 5

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 = 3일 때 누적합을 구해보면 아래와 같다.

2차원 배열

1	2	3
2	3	4
3	4	5

누적합

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

• 이때, (2, 2)부터 (3, 3)까지의 누적합은 (1, 1)부터 (3, 3)까지의 누적합 - (1, 1)부터 (1, 3)까지의 누적합 - (1, 1)부터 (3, 1)까지의 누적합 + (1, 1)까지의 누적합인 것을 알 수 있다.
  • 마지막에 (1, 1)까지의 누적합을 한 번 더해주는 이유는 (1, 1)부터 (1, 3)까지의 누적합과 (1, 1)부터 (3, 1)까지의 누적합에 (1, 1)이 중복되어 총 두 번 빼지기 때문임
• 즉, (y1, x1)부터, (y2, x2)까지의 누적합을 구하고자 할 때, 이를 구하는 점화식은 아래와 같이 정의할 수 있음
  • dp[y2][x2] = dp[y2][x2] - dp[y1 - 1][x2] - dp[y2][x1 - 1] + dp[y1 - 1][x1 - 1]

 

💻 소스코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

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] = graph[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]

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