[BOJ/C++] 21921 블로그

문제

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

풀이

🌟누적합(prefix sum) 문제

부분 배열의 합을 구하려면 원래 이중 for문을 이용해서 시간복잡도가 O(N²)이지만, 누적합을 이용하면 구간합을 구하는데 O(N) + 누적합 배열에서 임의의 구간의 합을 찾는데 O(1)이라 시간복잡도가 Good!

• 합을 미리 계산해두기 때문에 시간복잡도가 확 줄어들음
• 처음에 배열로 값 입력 받으면서 누적합 배열 같이 만들어주면 됨

처음에 accumulate()함수로 구간합 구하고, max_element()로 구간별 최댓값을 구하려고 했는데 터무니없이 시간초과 났다.

accumulate() : O(N)
max_element() : O(N)

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	int N, X;
	vector<int> v;
	cin >> N >> X;
	vector<int> prefix_sum(N + 1, 0);
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
		prefix_sum[i + 1] = prefix_sum[i] + tmp;
	}

	int ans1 = 0, ans2 = 0;
	for (int i = X; i <= N; i++) {
		int sum = prefix_sum[i] - prefix_sum[i - X];

		if (sum > ans1) {
			ans1 = sum;
			ans2 = 1;
		}
		else if (sum == ans1) {
			ans2++;
		}
	}

	if (ans1 == 0)	cout << "SAD";
	else {
		cout << ans1 << '\n' << ans2;
	}

	return 0;
}