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

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

21921번: 블로그

 

X일의 연속된 방문자 합의 가장 큰 값을 찾는 문제

 

보자마자 슬라이딩 윈도우를 떠올렸다.

 

첫번째 풀이 - 실패 (시간초과)

#include <bits/stdc++.h>
using namespace std;

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

	int n, x; cin >> n >> x;

	vector <int> vc;

	int maxN = 0;
	int days = 0;
	// 슬라이딩 윈도우

	for (int i = 0; i < n; i++) {
		int c; cin >> c;
		vc.push_back(c);

		int tmpN = 0;
		if (i + 1 >= x) {
			for (int j = -x; j < 0; j++) {
				tmpN += vc[i + j + 1];
			}
			if (tmpN >= maxN) {
				if (tmpN > maxN)
					days = 1;
				else if (tmpN == maxN) {
					days++;
				}
				maxN = tmpN;
			}
		}
	}

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

}

i번째 입력이 x보다 커질 때부터 (Out of range 방지) 한 번의 입력을 받을 때마다, for문을 i-x ~ i번까지 돌린 합을 구하고 최대합과 비교하여 크다면 갱신시켜주는 코드이다.

n의 범위가 250,000이어서 시간초과가 났다.

 

두번째 풀이 - 성공

#include <bits/stdc++.h>
using namespace std;

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

	int n, x; cin >> n >> x;

	vector <int> vc;

	int maxN = 0;
	int days = 0;
	// 슬라이딩 윈도우

	int tmpN = 0;
	for (int i = 0; i < n; i++) {
		int c; cin >> c;
		vc.push_back(c);

		if (i < x) {
			tmpN += c;
		}
		else {
			tmpN -= vc[i - x];
			tmpN += c;
		}

		if (tmpN >= maxN) {
			if (tmpN > maxN)
				days = 1;
			else if (tmpN == maxN)
				days++;
			maxN = tmpN;
		}
	}

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

}

실패 코드와의 다른 점은 매 입력마다 for문을 X번 돌리는 것이 아니라 새로운 입력이 들어오면 맨 왼쪽 원소(i - x번)를 제거하고 새로 입력 받은 i번 원소를 현재 값에 더해주는 것이다.

그 값이 현재까지의 최댓값보다 크다면 days를 1로 초기화, maxN을 갱신하고 최댓값과 같다면 days만 늘려주는 것이다.