▶실버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;
}
}
'Algorithm > Baekjoon' 카테고리의 다른 글
11057_오르막수 (0) | 2023.01.04 |
---|---|
2003_수들의 합 2 (0) | 2023.01.02 |
2583_영역 구하기 (0) | 2022.11.11 |
3184_양 (0) | 2022.11.10 |
12847_꿀 아르바이트 (0) | 2022.11.09 |