[백준] 11660 구간 합 구하기 5 (Python 파이썬)

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

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이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

---

풀이 과정

이 문제는 누적 합 으로 해결할 수 있다.

 

다음과 같은 표가 있다고 하자.

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

 

이제 표의 각각의 칸에는 그 칸까지의 누적합을 작성하자.

예를 들어, (2,2)에는 (0,0) ~ (2,2) 까지의 합을 더한 값이 들어간다.

누적합으로 작성한 표는 다음과 같다.

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

 

이 때, (1, 1) ~ (2, 2) 의 합계를 구하고 싶다면

(2,2)에 저장된 누적합에

(1,1)에 저장된 누적합을 빼주고

겹치는 부분인 (1,1)의 값(누적합이 아닌 고유의 그 값)을 더해주면 된다.

(1,1)칸은 두 번 뺐기 때문에 한 번 더해주어야 하는 것이다.

 

이를 파이썬 코드로 나타내면 다음과 같다.

import sys

input = sys.stdin.readline
n, m = map(int, input().split())

graph = []

for i in range(n):
  graph.append(list(map(int, input().split())))

acc = [[0]*(n+1) for _ in range(n+1)]

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

print(acc)

for i in range(m):
  x1,y1,x2,y2 = map(int, input().split())

  print(acc[x2][y2] - acc[x1-1][y2] - acc[x2][y1-1] + acc[x1-1][y1-1])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !