BOJ 19566) c++ 수열의 구간 평균

시간 제한 - 1s

메모리 제한 - 256MB

 

---

풀이

1. 부분 수열의 합 / 부분 수열의 길이 = 해당 부분 수열의 평균임을 이용해 풀이 (N까지의 누적합 / N = 평균)

2. (N까지의 누적 합 - x까지의 누적 합) / (N - x) = x부터 N까지의 평균 

인덱스	0	1	2	3	4	5	6
배열		1	1	1	1	1	1
누적합	0	1	2	3	4	5	6
평균	0	1	1	1	1	1	1

위 테이블에서 6까지의 평균은 당연히 1이다. 만일 찾으려는 값이 1이라면, 이를 만족하는 구간은 모든 구간인 N * (N + 1) / 2인 21이 나와야 함(1:1, 1:2, 1:3, 1:4, 1:5, 1:6, 2:2, 2:3 ••• 6:6)

3. 누적합을 구하고 평균을 계산해 해당 값이 나온 횟수를 구해준다. 

4. 평균을 계산하고 찾으려는 값 K와 평균의 차이가 몇 번 나왔는지 계산해 결과 값에 더해준다.(DP[sum - idx * K]++)

누적 합	인덱스	평균	DP[0]의 횟수	결과 값
1	1	1	1	0
2	2	1	2	0 + 1
3	3	1	3	1 + 2
4	4	1	4	3 + 3
5	5	1	5	6 + 4
6	6	1	6	10 + 5

평균이 K가 될 때마다 평균 - idx * K는 0이 됨.

5. 최종적으로 1부터 N까지의 합도 연산에 포함시킴, 결과 값 += DP[0]

입력

1 <= N <= 200,000, -1e9 <= K <= 1e9

수열 N개 입력 (입력 최적화)

 

자료구조

map<long long, int> 누적합 long long이 int번 나왔음을 기록

---

 

코드

#include <iostream>
#include <map>

using namespace std;
using ll = long long;

int main() {
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);

	ll n, k, tmp, input, cnt = 0, sum = 0;
	map<ll, ll> dp;
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> input;
		sum += input;		//	현재까지의 누적합
		tmp = sum - i * k;	//	tmp = 현재까지의 누적합 - 만들어야할 누적합
		cnt += dp[tmp]++;	//	tmp가 만들어질 수 있는 부분 배열 기록
	} cnt += dp[0];			//	전체 부분 배열 중 평균이 K가 되는 횟수 추가
	cout << cnt << endl;	//	결과 값
	return 0;
}

 

시간 복잡도

O(N)