백준 21921번 [블로그](C++) -yes6686- 티스토리

백준 문제 풀이: 21921 [블로그]

---

문제 링크: https://www.acmicpc.net/problem/21921

문제 설명:

블로그 방문자 수를 기록한 데이터에서 연속된 n일 동안 방문자 수의 최대값과 그 최대값이 나타난 횟수를 구하는 문제입니다.

만약 방문자 수가 0일 경우 "SAD"를 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[250001];

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

    int x, n;
    cin >> x >> n;
    
    int sum = 0;

    // 첫 n일의 합 구하기
    for (int i = 0; i < x; i++) {
        cin >> arr[i];
        if (i < n) sum += arr[i];
    }

    int maxVisitors = sum;
    int count = 1;

    // 슬라이딩 윈도우 기법을 사용하여 최대 방문자 수 탐색
    for (int i = n; i < x; i++) {
        sum = sum + arr[i] - arr[i - n];

        if (sum > maxVisitors) {
            maxVisitors = sum;
            count = 1;
        } else if (sum == maxVisitors) {
            count++;
        }
    }

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

    return 0;
}

예제 입력:

7 5
1 1 1 1 1 5 1

예제 출력:

9
2

---

코드 설명

• 핵심 알고리즘: 슬라이딩 윈도우 기법을 활용하여 연속된 n일 동안의 방문자 수를 효율적으로 계산합니다.
• 구현 세부사항:
  • 첫 번째 n일 동안의 방문자 수 합을 미리 계산합니다.
  • 그 후 arr[i]를 추가하고 arr[i - n]을 제외하는 방식으로 윈도우를 이동하면서 방문자 수를 갱신합니다.
  • 최대 방문자 수와 해당 횟수를 추적하며 비교합니다.
• 시간 복잡도: O(X), 슬라이딩 윈도우를 활용하여 한 번만 순회

---

결과

주어진 방문자 데이터에서 최적의 연속 기간을 찾아 최대 방문자 수와 그 횟수를 정확히 계산합니다. 슬라이딩 윈도우 기법을 연습하기 좋은 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!