[백준 11660] 구간 합 구하기 5

	# 백준 11660번 문제검색 링크 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.예를 들어, N = 4이고, 표가 아래와 같이 채워져  www.acmicpc.net

 

Key Point

• 합배열을 만드는 방법은 sum_array[i][j]= sum_array[i-1][j]+sum_array[i][j-1]-sum_array[i-1][j-1]+numbers[i][j] 이다.   *그림을 그려보면 이해하기 편하다
• 문제의 구간의 합을 구하기 위해서는 sum_array[x2][y2]-sum_array[x1-1][y2]-sum_array[x2][y1-1]+sum_array[x1-1][y1-1]의 공식을 사용하면 된다. *이것도 그림을 그려보면 편하다

 

 

문제 코드

import sys
input=sys.stdin.readline

N,M= map(int ,input().split())
numbers=[[0]*(N+1)]
sum_array=[[0]*(N+1) for _ in range(N+1)]

for _ in range(N):
    numbers.append([0]+list(map(int, input().split())))

for i in range(1,N+1): #합배열 구하기
    for j in range(1,N+1):
        sum_array[i][j]=sum_array[i-1][j]+sum_array[i][j-1]-sum_array[i-1][j-1]+numbers[i][j]

for _ in range(M): #문제에서 원하는 구간별의 합 구하기
    x1,y1,x2,y2=map(int,input().split())
    print(sum_array[x2][y2]-sum_array[x1-1][y2]-sum_array[x2][y1-1]+sum_array[x1-1][y1-1])