[C++/백준] 21921번 : 블로그

• 문제

https://www.acmicpc.net/problem/21921

알고리즘 분류 : 누적합

21921번: 블로그

• 코드

#include <iostream>
#include <vector>
using namespace std;
//21921번 블로그
//맨처음부터 x까지수를 배열에 넣은후 반복문을 통해 앞에만 넣고 뒤에를 빼면서 탐색
int main() {
int n = 0;
int x = 0;
cin >> n >> x;
vector <int> arr;
vector <int> srch;
int a = 0;
for (int i = 0; i < n; i++) {
cin >> a;
arr.push_back(a);
}
int sum = 0;
for (int i = 0; i < x; i++) {
sum += arr[i];
}
int presum = sum;
int term = 1;
for (int i = 0; i < n - x; i++) {
presum += arr[i + x] - arr[i];
if (presum > sum) {
sum = presum;
term = 1;
}
else if (presum == sum && presum != 0) {
term += 1;
}
}
if (sum == 0) {
cout << "SAD" << endl;
}
else {
cout << sum << endl;
cout << term << endl;
}
}

• 풀이

((평소보다 빨리 푼 것 같다는 생각으로 가볍게 코드를 짜고 제출하다가 c++을 사용하고 처음으로 시간 초과를 마주했다... 당황해서 문제를 다시보니 입력값 범위가 무려 25만까지로 이중 반복문을 절대 쓸 수 없었다. ㅎㅎ 열심히 고민해봤지만 도무지 모르겠어서 힌트만 얻자는 생각으로 문제를 검색했고 누적합 알고리즘을 써야한다는 것을 알게 되었다. 시간이 없다고 알고리즘 강의는 안보고 문제를 풀었더니 더 시간을 낭비했다ㅜㅜ ))

먼저 첫번째부터 x번째까지 수를 다 더해놓는다. 그다음 그 누적합에 앞의 수를 빼고 뒤에 수를 더하면 이중 반복문으로 탐색하지 않고 반복문 하나로 길이와 최대 방문자수를 구할 수 있다. 0이 아니면서 같은 기간의 수를 구하기 위해 if문으로 예외처리를 해야한다.