백준(baekjoon) 11660번: 구간 합 구하기 5(실버 1, 파이썬 PYTHON) - 누적 합

문제

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

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

 

 

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

11660번: 구간 합 구하기 5

 

import sys

N,M=map(int,sys.stdin.readline().split())
graph=[list(map(int,sys.stdin.readline().split())) for _ in range(N)]
sum_graph=[[0]*(N+1) for _ in range(N+1)]

for x in range(1,N+1):
  for y in range(1,N+1):
    sum_graph[x][y]=sum_graph[x][y-1]+sum_graph[x-1][y]-sum_graph[x-1][y-1]+graph[x-1][y-1]

for _ in range(M):
  x1,y1,x2,y2=map(int,sys.stdin.readline().split())
  print(sum_graph[x2][y2]-sum_graph[x2][y1-1]-sum_graph[x1-1][y2]+sum_graph[x1-1][y1-1])

 

※ 누적 합

 

 

● 먼저 N과 M을 입력받은 후, N개의 줄에 입력되는 각 숫자들을 배열로 만들어 graph라는 배열에 집어넣는다(graph는 2차원 배열이 됨). 그 후 행과 열의 크기가 N+1이고 초기 값이 0인 2차원 배열 sum_graph를 만들어준다.

 

● x,y 의 범위는 1부터 N 까지 변하고, sum_graph[x][y] 에는 graph[0][0] 부터 graph[x-1][y-1] 까지 직사각형으로 둘러쌓인 수들의 합이 들어간다. sum_graph[x][y] 의 값을 구하기 위해서는 sum_graph[x][y-1] 의 값과 sum_graph[x-1][y] 의 값을 더하고 중복으로 더해진 sum_graph[x-1][y-1] 의 값을 빼준 뒤 graph[x-1][y-1] 에 들어가 있는 수를 더해주면 된다.

 

● 그 후 M개의 줄에서 각각 x1, y1, x2, y2 를 입력받은 뒤 sum_graph[x2][y2] 에서 sum_graph[x2][y1-1] 과 sum_graph[x1-1][y2] 값을 빼준 후 중복적으로 빼버린 sum_graph[x1-1][y1-1] 의 값을 더해주어 이 값을 각각 출력해주면 된다(그림으로 잘 설명해놓은 링크를 아래에 첨부해두었다).

 

 

 

 

https://castlerain.tistory.com/100

[백준] 11660 구간 합 구하기 5 (python) - 누적 합 (2차원) 정리