★Prefix Sum 중급 - 5문제()★

🐰 누적합 유형은 주로 어려운 난이도 다양한 알고리즘 유형의 답을 구하는 과정에서 많이 사용된다. 단독으로 사용되는 경우만 일부 문제를 골라 정리해봄

---

★ 11441 합 구하기 ★

 

import sys
input=sys.stdin.readline
N=int(input())
B=[]
a=0
for i in map(int,input().split()):
    a+=i
    B.append(a)
for _ in range(int(input())):
    a,b=map(int,input().split())
    if a==1:print(B[b-1])
    else:print(B[b-1]-B[a-2])

 

🐰 누적합을 구하기 위한 구간을 만든 뒤, 구간 B에서 원하는 구간만큼 바로 indexing으로 B[b-1] - B[a-2] 연산해주면 완료!

---

★ 11659 구간 합 구하기 4 ★

 

#indexing over slicing
N, M = map(int, input().split()) 
numbers = list(map(int, input().split()))

totals = []
answers = []
total = 0

for i in range(N):
    total += numbers[i]
    totals.append(total)   

for _ in range(M):
    i, j = map(int,input().split())
    if i == 1:
        answers.append(totals[j-1])
    else:
        answers.append(totals[j-1] - totals[i-2])

for answer in answers:
    print(answer)

 

🐰 누적합 list를 만들 때 for문 필요없이 itertools의 accumulate 함수를 사용해서도 만들 수 있다.

 

import sys
input = sys.stdin.readline
from itertools import accumulate

#indexing over slicing
N, M = map(int, input().split()) 
numbers = list(map(int, input().split()))

totals = list(accumulate(numbers))
answers = []

for _ in range(M):
    i, j = map(int,input().split())
    if i == 1:
        answers.append(totals[j-1])
    else:
        answers.append(totals[j-1] - totals[i-2])

for answer in answers:
    print(answer)

---

★ 17390 이건 꼭 풀어야 해! ★

 

import sys
input=sys.stdin.readline

N,Q=map(int,input().split())
l=sorted(list(map(int,input().split())))
t=0
culsum=[0]
for i in l:
    t+=i
    culsum.append(t)
for k in range(Q):
    L,R=map(int,input().split())
    print(culsum[R]-culsum[L-1])

 

🐰 정렬하고 구간 합 풀면 끝! itertools의 accumulate 사용하면 좀 더 시간 단축됨

---

★ 11969 Breed Counting ★

 

import sys
input=sys.stdin.readline

N,Q=map(int,input().split())
cows=[int(input()) for _ in range(N)]
prefix_sum=[[0,0,0] for _ in range(N)]

for i in range(0,N):
    if i ==0:prefix_sum[i][cows[i]-1] = 1
    if cows[i]==1:
        prefix_sum[i][0] = (prefix_sum[i-1][0]) + 1
        prefix_sum[i][1] = prefix_sum[i-1][1]
        prefix_sum[i][2] = prefix_sum[i-1][2]
    elif cows[i]==2:
        prefix_sum[i][0] = prefix_sum[i-1][0]
        prefix_sum[i][1] = (prefix_sum[i-1][1]) + 1
        prefix_sum[i][2] = prefix_sum[i-1][2]
    else:
        prefix_sum[i][0] = prefix_sum[i-1][0]
        prefix_sum[i][1] = prefix_sum[i-1][1]
        prefix_sum[i][2] = (prefix_sum[i-1][2]) + 1

for _ in range(Q):
    s,e=map(int,input().split())
    if s==1: print(*prefix_sum[e-1])
    else:
        l=[]
        x=prefix_sum[e-1]
        y=prefix_sum[s-2]
        for a,b in zip(x,y):
            l.append(a-b)
        print(*l)

 

🐰 주어진 cow 개체 수의 index 위치 구간을 알고 나면, 주어진 구간 내의 cow 1, 2, 3 개체 수를 각각 구하는 문제

 

🐰 구간별 합을 개체수 별로 각각 구한 뒤, 누적합 개념에 맞게 큰 누적 합 - 작은 누적 합을 구함

---

★ 13900 순서쌍의 곱의 합 ★

 

import sys
input=sys.stdin.readline
N=int(input())
l=list(map(int,input().split()))
total=sum(l)
ans=0
for i in range(N-1):
    total-=l[i]
    ans+=l[i]*total
print(ans)

 

🐰 전체 순서쌍의 mulsum은 위와 같이 전체 total에서 앞의 원소를 for문으로 돌리며 한개씩 빼나가면서 계속 더해나가면 된다. 전체 누적합을 계속 빼나가며 for문 한 번으로 모든 경우의 mulsum을 구할 수 있는 전체 순서쌍(두 개 원소)의 합 구하기 문제유형

---