[Silver 3] 21921 블로그

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

21921번: 블로그

 

이 문제는 투 포인터를 사용해서 해결할 수 있다.

이 문제의 핵심은 구간 합을 반복문이 아닌 누적 합을 사용해서 해결해야한다는 것이 핵심이다.

 

구간 합을 반복문을 사용하면 O(N^2)이 되어 시간 초과가 발생한다.

따라서 값을 계속 해서 누적하고 합이 X보다 커지면 end 지점의 값을 빼고 end 포인터를 이동시킨다.

이러면 구간의 합을 계속해서 누적할 수 있다.

 

#include<iostream>

using namespace std;

int N, X;
int arr[250001];
int result = 0;

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

	cin >> N >> X;

	for (int i = 0; i < N; i++)
		cin >> arr[i];

	int start = 0, end = 0;
	int counter = 0;
	int calc = arr[end];
	result = arr[end];

	while (start < N) {
		int person = 0;
		start++;

		if (start - end >= X) {
			calc -= arr[end];
			end++;
		}

		calc += arr[start];
		if (calc > result) {
			counter = 1;
			result = calc;
		}
		else {
			if (calc == result)
				counter += 1;
		}
	}
	if (result == 0)cout << "SAD" << '\n';
	else {
		cout << result << '\n';
		cout << counter << '\n';

	}
	return 0;
}