Skip to main content

11660 - 구간 합 구하기 5

info

풀이 키워드​

스포주의

2차원 누적합 DP


풀이 코드​

info
  • 메모리: 106044 KB
  • 시간: 744 ms
import sys
input = sys.stdin.readline

table = []
presum = []
n, m = 0, 0

def calc_presum():
    global table, presum
    for i in range(2, n+2):
        isum = 0
        for j in range(2, n+2):
            isum += table[i-1][j-1]
            presum[i-1][j-1] = presum[i-2][j-1] + isum

def solution():
    x1, y1, x2, y2 = map(int, input().split())
    ans = presum[x2][y2] - presum[x2][y1-1] - presum[x1-1][y2] + presum[x1-1][y1-1]
    print(ans)
    

if __name__ == '__main__':
    n, m = map(int, input().split())
    table.append([0] * (n+1))
    
    for y in range(1, n+1):
        table.append([0])
        table[y].extend(list(map(int, input().split())))
    
    presum = [[0 for _ in range(n+1)] for __ in range(n+1)]
    calc_presum()
    
    for tc in range(m):
        solution()
  • calc_presum: O(N^2)
    • 1 <= N <= 1024 이므로 N^2 = 약 100만
    • 파이썬 1초는 대략 2000만 --> OK
  • solution: O(1)

풀이 해설​

부분합

이미지 출처


메모​

  • calc_presum에서 i와 j의 값을 고려하는 부분이 어느정도 지성을 요구함