2023.03.03 구간 합 구하기 5[PYPY]

 

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

11660번: 구간 합 구하기 5

 

import sys
input = sys.stdin.readline

n,m = map(int,input().split()) # 크기와 횟수

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

qus = [list(map(int,input().split())) for _ in range(m)]
#print(maps)
for i in range(n):
    for j in range(n):
        if j :
            maps[i][j] += maps[i][j-1]  
#print(qus)
#print(maps)
for i in range(m):
    sums = 0
    for j in range(qus[i][0]-1,qus[i][2]):
        if qus[i][1] == 1:
            sums += maps[j][qus[i][3]-1]
        else:
            sums += maps[j][qus[i][3]-1] - maps[j][qus[i][1]-2]
    print(sums)

구간합을 단순히 for 문으로 돌렸다. python은 시간초과가 나서 pypy로 돌려서 성공했다.

생각나는 다른 방법으로는 구간을 나눠서 가장 큰 범위 - 양 옆 2개 범위 + 겹치는 범위로 구하면 될거 같다.