self.winter.(13). Prefix Sum (구간합, 누적합, 부분합) _ 백준 [11659, 11660, 10986]

🧐  Prefix   Sum 

Prefix Sum, 구간합, 누적합, 부분합이라 불리며 해당 구간에 대한 합을 빠르게 구하기 위한 알고리즘은 매우 간단하다.

원리는 아래와 같다.

1. 합 배열 S를 만드는 공식
S[i] = S[i-1] + a[i]

2. i~j까지의 구간합을 구하는 공식
S[j] - S[i-1]

이를 이용하면 다음과 같이 일정 구간에서의 합을 빠르게 (시간복잡도를 줄이면서) 구할 수 있다.

  S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]
  S[1] = A[0] + A[1]
--------------------------------------------------
∴ S[5] - S[1] = A[2] + A[3] + A[4] + A[5]

 

 

🧐 백준 11659 (구간 합 구하기)    Silver III 

🤫  solution_11659

n, m = map(int, input().split())
num = list(map(int, input().split()))

prefix_sum = [0]
p_sum = 0
for i in num:
    p_sum += i
    prefix_sum.append(p_sum)


for _ in range(m):
    i, j = map(int, input().split())
    print(prefix_sum[j] - prefix_sum[i-1])

 

 

 

🧐 백준 11660(구간 합 구하기 _ 이차원 배열)    Silver I 

🤫  Algorithm 

 

🤫  solution_11660

n, m = map(int, input().split())
num = [list(map(int, input().split())) for i in range(n)]

S = [[0 for i in range(n + 1)] for i in range(n + 1)]

for i in range(n):
    for j in range(n):
        S[i + 1][j + 1] = (S[i][j + 1] + S[i + 1][j] - S[i][j]) + num[i][j]

for i in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    print(S[x2][y2] - (S[x2][y1-1] + S[x1-1][y2]) + S[x1-1][y1-1])

 

 

 

🧐 백준 10986(구간 합 구하기)    Gold III 

부분 합 개념을 이용해서 풀 때, 부분 합을 계산한 배열을 i, j로 순차적으로 접근할 경우 
O(n^2)으로 시간 초과가 발생하므로 다른 풀이 방법이 필요하다.

🤫  Algorithm 

미리 구해둔 prefix sum에서의 부분합은 S[j] - S[i - 1]의 과정이다.

이때, S[j]와 S[i-1]이 각각 m으로 나눴을 때의 나머지가 동일하다면?
S[j] - S[i - 1] 연산 후 나머지는 0이 되기에 m으로 나눠 떨어진다.

결국 m으로 나눠떨어지는 부분합을 구하는 것은 
나머지가 동일한 idx 중 임의로 nC2를 선택하는 것과 같으므로 다음 알고리즘을 거친다.

[1] [2] [3] [1] [2] -> [0] [1] [3] [6] [7] [9] -> [0] [1] [0] [0] [1] [0] 
-> [0 : 4, 1 : 2] -> 6 + 1 -> 7

 

🤫  solution_10986

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
num_list = list(map(int, input().split()))

rest_list = [0 for _ in range(m)]
rest_list[0] = 1

prefix_sum = 0
for i in range(n):
    prefix_sum += num_list[i]
    rest = prefix_sum % m
    # 나머지 값에 따라서 idx 정보 저장
    rest_list[rest] += 1

cnt = 0
for i in rest_list:
    cnt += i*(i - 1) // 2

print(cnt)