[BOJ/백준] 19566 수열의 구간 평균

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()

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

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


prefix_sum = [0] + arr[:]
result = 0
num_dict = defaultdict(int)
for i in range(1,N+1):
    prefix_sum[i] += prefix_sum[i-1]
    calc = prefix_sum[i] - M*i

    result += num_dict[calc]
    num_dict[calc] += 1


print(result+num_dict[0])

몇달 전에 푼 문제라 정확히 복기는 못하지만, 현재 생각 나는대로 복기를 할려고 한다.

 

 이 문제는 누적합을 이용해 구간의 평균합의 개수를 구하는 것이다.

 

 

현재까지의 누적합에서 지금까지의 평균의 총합을 빼주게 된다면, 

 

현재 위치에서 평균이 되기 위해 사라져야할 값이 보인다.

 

이 점을 이용해 푸는 문제이다.

 

구해야하는 평균이 K일때

 

즉 현재의 누적합 - 구간*K 을 했을때 나오는 값을 calc이라 했을 때,

 

이 calc 만큼만 사라지면 현재 구간 앞에서 얻을 수 있는 평균이 K인 구간의 개수가 되는 것이다.

 

이 문제는 누적합에서 구간의 평균합을 뺀 숫자와 일치하는 개수를 계속 누적해서 더해주면 풀 수 있는 문제이다.

 

그리고 마지막에 0을 더해준 이유는 현재 구간의 앞에서 나올 수 있는것을 더해준 것이니,

전체 구간에서 더해줄 필요가 있어서, 마지막에 더해주는 것이다.

 

6달전에 풀었던 것을 다시 복기할려니 정확하게 설명은 못했지만, 위와 같은 방법을 활용하면 된다.