21921_블로그

▶실버3

풀이

누적 합을 이용한다. 예제 1번을 예시로 들면 n = 5, x = 2

1	4	2	5	1
1	5	7	12	13

로 누적 합을 구한다. 이때, x = 2이므로 arr[i] - arr[i - 2]를 한 값들을 벡터에 넣고 내림차순 정렬한 뒤 최댓값이 몇 개 있는지 센다. 벡터에 들어가는 값은 6, 7, 6인데 실제로는 5, 6, 7, 6이어야 한다. 따라서 배열 맨 앞에 0을 넣고 구하는 것이 맞다.

코드

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

int visitor[250001];
vector <int> sum;

bool compare(int i, int j) {
	return j < i;
}

int main(void) {
	cin.tie(0); cout.tie(0);
	int n, x;
	cin >> n >> x;

	visitor[0] = 0; //첫 번째 값은 0
	cin >> visitor[1];
	if (x == 1) { //x = 1일 때, 첫 번째 유효 값을 sum에 넣어준다.
		sum.push_back(visitor[1]);
	}
	
	for (int i = 2; i <= n; i++) {
		cin >> visitor[i];
		visitor[i] = visitor[i - 1] + visitor[i]; //누적합 구하기
		if (i >= x) {
			sum.push_back(visitor[i] - visitor[i - x]);
		}
	}
	
	
	sort(sum.begin(), sum.end(), compare); //내림차순 정렬
	int cnt = 0;
	for (int i = 0; i < sum.size(); i++) {
		if (sum[0] == sum[i]) { //sum[0]이 최댓값
			cnt++;
		}
		else
			break;
	}
	if (sum[0] == 0) {
		cout << "SAD";
	}
	else {
		cout << sum[0] << "\n" << cnt;
	}
	
}