C++ 백준 21921번 : 블로그

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

21921번: 블로그

문제

찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.

요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.

 

찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.

찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.

입력

첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.

둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.

출력

첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.

만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

---

풀이

슬라이딩 윈도우 알고리즘을 이용해서 해결

 

슬라이딩 윈도우 알고리즘이란?

- 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘

 

작동 원리

배열에 1,2,3,4,5 가 있을 때 인접해있는 숫자중에 제일 큰 수는?라는 문제에서

[1,2],3,4,5

1,[2,3],4,5

1,2,[3,4],5

1,2,3,[4,5]

이렇게 []안에 맨 첫 번째 숫자와 ] 뒤 숫자만 갱신하는 알고리즘이다. 

---

#include <bits/stdc++.h>
using namespace std;
int arr[250001] = { 0, };
int main(void)
{
	int day,num;
	cin >> day >> num;
	for (int i = 0; i < day; i++) {
		int tmp;
		cin >> tmp;
		arr[i] = tmp;
	}
	int compare = 0;
	int plag = 1;
	int max = 0;
	for (int i = 0; i < num; i++) { // 초기값
		max += arr[i];
		compare += arr[i];
	}

	for (int i = num; i  <day; i++) {
		// 양쪽 끝 원소만 갱신
		compare -= arr[i-num]; 
		compare += arr[i]; // 

		if (max == compare) { // max가 같을 때 
			plag++; // 기간
		}
		else if (max < compare) { // max 갱신
			plag = 1;
			max = compare;
		}
	}
	if (max == 0) { // 최대 방문자 수 0명
		cout << "SAD" << '\n';
	}
	else {
		cout << max << '\n';
		cout << plag << '\n';
	}

	return 0;
}

---

참고사이트

https://ji-musclecode.tistory.com/37

슬라이딩 윈도우 알고리즘(Sliding Window) (feat. 투 포인트)