백준 11659 구간 합구하기 4

알고리즘: 누적합

#1. 브루트포스 풀이 -> 시간 복잡도 O(NM)-> 10초 걸림 시간 초과 
N,M  = map(int, input().split()) 
lst= list(map(int, input().split()))

l = [] 
for _ in range(M): 
	a, b = map(int, input().split())
    l.append(a,b) 
    print(sum(l[a-1: b]))

for문 M번안에 N번 반복해야하므로 시간 초과가 난다. -> 누적합 알고리즘을 이용하자.

import sys 
input = sys.stdin.readline
N, M = map(int, input().split())
lst = list(map(int, input().split()))

#미리 누적합 구해놓기 
total_s = [0] * N+1 #인덱스를 1부터 하고 싶어서 
for i in range(1, N+1): 
	total_s[i] = total_s[i-1] + lst[i]

for _ in range(M): 
	print(total_s[b] - total_s[a-1])
    

백준 11660 구간합 구하기 5

import sys 
input = sys.stdin.readline

N, M = map(int, input().split()) 

dp = [[0] * (N+1) for i in range(N+1)]

matrix = [] 
for _ in range(N): 
	matrix.append(list(map(int, input().split())))

dp = [[0]* (N+1) for i in range(N+1)]

for i in range(N+1): 
	for j in range(N+1): 
		dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1]
		
for _ in range(M): 
	x1,y1,x2,y2 = map(int, input().split()) 
	result = dp[x2][y2] - dp[x1-1][y2] -dp[x2][y1-1]  +dp[x1-1][y1-1]
	print(result)