누적 합(Prefix)

특정 수열이 주어지고, 그 수열에서 특정 구간의 값을 구하는 쿼리가 반복적으로 들어올 때 주로 사용하는 개념.

일반적으로 문제 풀이를 진행할 경우 O(n2)의 시간 복잡도이나, 누적 합을 사용하게 될 시 O(n)의 시간 복잡도를 가지게 된다.

해결가능한 문제

백준 10986
https://www.acmicpc.net/problem/10986

문제풀이

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

# 나머지를 담는 배열 생성
reminder = [0] * M
# 초깃값 설정
reminder[arr[0] % M] = 1

for i in range(1, N):
    arr[i] += arr[i-1] # 누적합
    reminder[arr[i] % M] += 1   # 해당 나머지 값 추가

ans = reminder[0]   # 나머지가 없을 때의 값 더해주기
for re in reminder:
    ans += re * (re-1) // 2 # nC2 조합으로 답 갱신
print(ans)

초기에는 누적합 개념을 사용하지 않고 2차원 배열로 문제풀이를 진행하였으나, 시간초과 에러를 맞이했다.
그 이후 접근 방식으로
1. 누적합 적용
2. 해당 합에 대한 나머지 값에 해당하는 배열 값 갱신해주기
3. 나머지 값에 대해 nC2로 정답 갱신해주기

를 진행하였다.

출처 : https://www.crocus.co.kr/854