[백준] 11660번: 구간 합 구하기 5 (Silver) (python)

11660번:  구간 합 구하기 5

---

문제 )

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

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

 

 

여기서 (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을 기준으로 설명하면 

주어진 표의 누적합은 다음과 같이 만들어진다.

 

 

해당 구간의 합을 구하고 싶으므로

 

빨간 원들을 더하고, 검은 원을 빼주게 되면 해당 구간의 합이 계산된다.

 

 

이를 식으로 표현하면,

 

import sys
n, m = map(int, sys.stdin.readline().strip().split())
# 누적합을 만들기 위한 패딩
li = [[0] * (n + 1)] + [[0] + list(map(int, sys.stdin.readline().strip().split())) for i in range(n)]
prefix = [[0] * (n + 1) for i in range(n + 1)]
 
# 누적합 만들기
for i in range(1, n + 1):
    for j in range(1, n + 1):
        prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + li[i][j]
 
print()
pprint(prefix)
# 구간 합 구하기
for i in range(m):
    a, b, c, d = map(int, sys.stdin.readline().strip().split())
    print(prefix[c][d] + prefix[a - 1][b - 1] - prefix[a - 1][d] - prefix[c][b - 1])
 

와 같이 코드가 짜여진다.

---

출처 : https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5