[백준_11660] 구간 합 구하기 5 python

grid 굳이 저렇게 받지 않아도 된다.

입력 어케해야 저렇게 앞에 0을 넣을 수 있을까 고민해봤는데

굳이 그럴 필요가 없었다.

dp만 그렇게 만들어주면 된다.

# 입력 속도 개선
import sys
input = sys.stdin.readline

# n, m 입력
n, m = map(int, input().split())

# grid
grid = [
    list(map(int, input().split())) for _ in range(n)
]

# dp 설계
dp = [
    [0] * (n+1) for _ in range(n+1)
]

# dp채워넣기
for i in range(1, n+1):
    for j in range(1, n+1):
        dp[i][j] = dp[i][j-1] + grid[i-1][j-1]

# x1, y1, x2, y2 입력받기
for _ in range(m):
    x1, y1, x2, y2, = map(int, input().split())

    # ans 설정
    ans = 0

    # ans 구하기
    for i in range(x1, x2 + 1):
        ans += dp[i][y2] - dp[i][y1-1]
    
    #출력
    print(ans)

입력속도 개선시키지 않으면 시간초과 뜨니 주의