11660번 구간 합 구하기5(Silver1)

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

11660번: 구간 합 구하기 5

 

import sys

n,m=map(int,sys.stdin.readline().split())
array=[]
prefixSum=[[0 for _ in range(n+1)] for _ in range(n+1)]

for i in range(n):
    array.append(list(map(int,input().split())))
for i in range(1,n+1):
    for j in range(1,n+1):
        prefixSum[i][j]=prefixSum[i-1][j]+prefixSum[i][j-1]\
                        -prefixSum[i-1][j-1]+array[i-1][j-1]
for i in range(m):
    x1,y1,x2,y2=map(int,sys.stdin.readline().split())
    print(prefixSum[x2][y2]-prefixSum[x1-1][y2]\
        -prefixSum[x2][y1-1]+prefixSum[x1-1][y1-1])

누적합과 구간합을 사용하여 풀 수 있는 문제였다.

 

다만 입력에서 input을 사용하면 시간 초과 문제가 발생했다.

위 문제처럼 반복문으로 여러 줄의 입력을 할 때 시간초과를 피하기 위해서는

sys.stdin.readline()을 사용해야 한다.