21921번 - 블로그 | 슬라이딩 윈도우 알고리즘 (C++)

---

문제

---

풀이

슬라이딩 윈도우 알고리즘을 이용해 풀이했다.

 

아래의 문제와 풀이 과정이 유사하지만, 이 문제의 다른 점은 가장 많이 들어온 방문자 수와 함께 기간의 개수도 함께 출력해야 하는 것이다.

 

예를 들어 예제 입력 2의 경우에는 '1 1 1 1 5', '1 1 1 5 1'로 총 방문자 수가 9인 기간 두 개가 있기 때문에 출력 값이 '9 2'가 된다.

 

따라서, 기간의 개수를 세기 위해 cnt 값을 추가해주어야 한다.

 

2559번 - 수열 | 슬라이딩 윈도우 알고리즘 (C++)

 

  1. 0부터 x-1까지는 모두 sum에 더한다. 이때, 최대가 되는 합을 저장할 answer에 sum의 값을 넣는다.

	for (int i = 0; i < x; i++) {
		sum += arr[i];
	}

	answer = sum;
	cnt = 1;

 

 

  2. x부터 n-1까지는 arr[i]는 sum에 더하고, arr[i - k]는 sum에서 뺀다. answer과 sum 중 최댓값을 answer에 저장한다.

    최대 조회수인 기간이 갱신되면(sum > answer), cnt를 1로 초기화 해야한다.

    또한, 같은 최대 조회수 기간이 더 있다면(sum == answer), cnt 값을 1 증가시켜야한다.

	for (int i = x; i < n; i++) {
		sum += arr[i];
		sum -= arr[i - x];
		if (sum > answer) {
			answer = sum;
			cnt = 1;	// 최대 조회수인 기간이 갱신되면, cnt도 1로 초기화
		}
		else if (sum == answer) {
			cnt++;		// 같은 최대 조회수인 기간이 더 있다면 cnt++
		}
	}

 

 

  3. answer이 0인 경우에는 SAD를 출력, 아닌 경우에는 answer과 cnt를 차례로 출력한다.

 

	if (answer == 0) {
		cout << "SAD";
	}
	else {
		cout << answer << "\n";
		cout << cnt;
	}

---

코드

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

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

	int n, x, cnt = 0, sum = 0, answer, max = -1;
	cin >> n >> x;

	int arr[250001];

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	for (int i = 0; i < x; i++) {
		sum += arr[i];
	}

	answer = sum;
	cnt = 1;

	for (int i = x; i < n; i++) {
		sum += arr[i];
		sum -= arr[i - x];
		if (sum > answer) {
			answer = sum;
			cnt = 1;
		}
		else if (sum == answer) {
			cnt++;		// 최대 조회수인 기간이 더 있다면 cnt++
		}
	}

	if (answer == 0) {
		cout << "SAD";
	}
	else {
		cout << answer << "\n";
		cout << cnt;
	}

	return 0;
}

 

---

결과