백준 알고리즘 11660번 : 구간 합 구하기 5 파이썬 코드 <문제풀이>

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

11660번: 구간 합 구하기 5

 

import sys;
input=sys.stdin.readline

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

for i in range(N):
    for j in range(1,N+1):
        psum[i][j]=psum[i][j-1]+grid[i][j-1]


for _ in range(M):
    x1,y1,x2,y2=map(int,input().split())
    ans=0
    x1-=1
    y1-=1
    
    for i in range(x1,x2):
        ans += psum[i][y2]-psum[i][y1]
    print(ans)

누적합의 2차원 배열 버전입니다.

 

! python3 로 제출하면 시간초과가 발생합니다.

! pypy로 제출하면 accept를 받을 수 있습니다.