[백준 11660] 구간 합 구하기 5 파이썬
https://www.acmicpc.net/problem/11660
11660번: 구간 합 구하기 5
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네
www.acmicpc.net
이차원 배열의 사각형 부분의 합을 구하는 문제입니다.
먼저 지시가 들어올 때마다 해당 사각형 부분의 인덱스를 모두 확인하여 합을 구하는 방법을 떠올릴 수 있습니다.
예시 배열의 경우, 이러한 방법으로 1,1부터 4,4 까지 전부 더하면 64임을 알 수 있습니다.
위와 같은 방법으로 제한 조건의 끝인 (1, 1)부터 (1024,1024)까지의 합을 10만번 구해야 한다고 생각해 봅니다.
한 번 구하는 데에 약 10만 번의 연산이 필요하고, 10만번 구하는 데에는 약 100억번의 연산이 필요합니다. 따라서 위의 방법으로는 1초 안에 문제를 풀 수 없기 때문에 다른 방법을 생각해 봅니다.
1차원 배열에서는 어느 구간의 합을 여러 번 구해야 할 때 누적 합을 이용하였습니다. 위의 문제도 같은 방식으로 생각합니다.
예시에서 주어진 (2,2)부터 (3,4)까지의 사각형 부분의 합을 구해야 한다면 다음과 같이 구할 수도 있습니다.
검은 부부분의 합 - 가로 빨간 부분의 합 - 세로 빨간 부분의 합 + 초록 부분 을 구하면 위의 파란 구간의 합을 구한 것과 같은 결과를 얻게 됩니다. 위의 계산 결과를 누적합으로 표현한다면 다음과 같이 나타낼 수 있습니다.
검정색 값은 검정색 사각형 부분의 합, 나머지 색 또한 그 색 사각형 부분의 합입니다.
이와 같이 큰 부분의 누적합을 구한 뒤에 필요 없는 부분은 빼고 두번 빠진 부분(초록색)은 다시 더하여 주는 방법을 통하여 파란색 구간의 합을 계산할 수 있었습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
from sys import stdin
n,m=map(int,stdin.readline().split())
a=[[0 ]*(n+1) ]
for i in range(n) :
b= list(map(int,stdin.readline().split()))
b.insert(0,0)
a.append(b)
#print(a)
#for i in range (n+1):
# print(a[i])
for i in range (n+1) :
for j in range (1,n+1) :
a[i][j]+=a[i][j-1]
for i in range (1,n+1) :
for j in range (n+1) :
a[i][j]+=a[i-1][j]
#for i in range (n+1):
# print(a[i])
for i in range (m) :
x1,y1,x2,y2=map(int,stdin.readline().split())
ans= a[x2][y2] - a[x1 -1 ][y2] - a[x2][y1-1] + a[x1-1][y1-1]
print(ans)
|
cs |