[백준 파이썬 11659번]구간 합 구하기4★누적 합(prefix sum) 알고리즘★더한것에 특정 열 빼기!

VER 2.0

import sys

T = list(map(int , sys.stdin.readline().rstrip().split(' ')))

M = T[0]

n = T[1]

N = list(map(int , sys.stdin.readline().rstrip().split(' ')))
res , res2 = [0] , []
prefix_sum = 0
for i in range(M):
    prefix_sum += N[i]
    res.append(prefix_sum)
for i in range(n):
    T  = list(map(int , sys.stdin.readline().rstrip().split(' ')))
    res2.append(res[T[1]] - res[T[0] -1])
for i in res2:
    print(i)

 

0	5	4	3	2	1
0	5	9	12	14	15

==> prefix 할 때 앞에 값 0으로 초기화해주어야 한다!

==> 2부터 4까지의 합 ==> 14 - 5 = 9

==> 1부터 4까지의 합 ==> 14 - 0  = 14 

 

 

VER 1.0

import sys

A = list(map(int , sys.stdin.readline().split(' '))) #N = 개수 , M= 합을 구해야 하는 횟수
B = list(map(int , sys.stdin.readline().split(' '))) #N개의 개수
res= []
for i in range(A[0]-1):
    #B= [5,4,3,2,1]
    B[i+1] += B[i] #B[1] += B[0] = [5,9,3,2,1]
    #B[2] += B[1] = [5,9,12,2,1]
    #B[3] += B[2] = [5,9,12,14,1]
    #B[4] += B[3] = [5,9,12,14,15]
B = [0] + B
#B = [0,5,9,12,14,15]
for i in range(A[1]):
    C = list(map(int, sys.stdin.readline().split(' ')))
    res.append(B[(C[1])] - B[(C[0]-1)])
for j in res:
    print(j)

누적 합(prefix sum) 알고리즘

 

구하려 하는 구간 i, j에 해당하는 두 원소의 차를 구해 그 구간의 합을 구하는 방식을 사용한다.