[백준]/C++

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

경우42 2023. 12. 31. 18:56
반응형

 

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

 

21921번: 블로그

첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다

www.acmicpc.net

 

#문제 해결 방법

이 문제를 해결하기 위한 로직은 '슬라이딩 윈도우' 기법을 사용합니다. 이 기법은 일정 범위의 데이터를 순차적으로 이동시키면서 연산을 수행하는 방법입니다. 구체적으로, 문제의 해결 로직은 다음과 같습니다:

  1. 초기화:
    • maxVisitor: 최대 방문자 수를 저장하는 변수입니다. 이를 0으로 초기화합니다.
    • nowVisitor: 현재 윈도우(즉, 연속된 X일)의 방문자 총합을 저장하는 변수입니다.
    • count: 최대 방문자 수를 가지는 기간의 수를 카운트하는 변수입니다.
  2. 첫 번째 윈도우 설정:
    • 처음 X일 동안의 방문자 수를 nowVisitor에 누적합니다.
    • 이 누적된 값이 초기 최대 방문자 수(maxVisitor)가 됩니다.
  3. 슬라이딩 윈도우 이동:
    • 윈도우를 한 칸씩 오른쪽으로 이동시키며 새로운 X일 동안의 방문자 수를 계산합니다.
    • 이를 위해 윈도우의 가장 왼쪽 값을 빼고, 새로운 오른쪽 값을 더합니다.
    • 즉, nowVisitor = nowVisitor - visitors[start] + visitors[end + 1] 연산을 수행합니다.
  4. 최대 방문자 수 갱신 및 카운트:
    • 이동할 때마다 nowVisitor가 현재의 maxVisitor보다 크면, maxVisitor를 nowVisitor로 업데이트하고 count를 1로 설정합니다.
    • nowVisitor가 현재 maxVisitor와 같다면, 같은 최대값을 가진 또 다른 기간이 있음을 의미하므로 count를 1 증가시킵니다.
  5. 결과 출력:
    • 모든 가능한 윈도우를 검사한 후, maxVisitor가 0이면 "SAD"를 출력합니다. 이는 최대 방문자 수가 한 번도 0을 초과하지 않았음을 의미합니다.
    • maxVisitor가 0이 아니라면, maxVisitor와 count를 출력합니다.

이 로직을 따르면, 주어진 일수 N 동안의 방문자 데이터를 효율적으로 처리하여 �일 동안의 최대 방문자 수와 그러한 기간이 몇 번 있는지를 정확하게 계산할 수 있습니다.

#전체 코드

 

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

typedef long long ll;

int main() {
    int N, X;
    cin >> N >> X;

    vector<int> visitors(N);
    for (int i = 0; i < N; i++) {
        cin >> visitors[i];
    }

    ll maxVisitor = 0, nowVisitor = 0;
    int count = 0;

    // 초기 윈도우 설정
    for (int i = 0; i < X; i++) {
        nowVisitor += visitors[i];
    }
    maxVisitor = nowVisitor;

    // 슬라이딩 윈도우
    for (int start = 0, end = X - 1; end < N; start++, end++) {
        if (nowVisitor > maxVisitor) {
            maxVisitor = nowVisitor;
            count = 1;
        } else if (nowVisitor == maxVisitor) {
            count++;
        }
        if (end + 1 < N) {
            nowVisitor = nowVisitor - visitors[start] + visitors[end + 1];
        }
    }

    if (maxVisitor == 0) {
        cout << "SAD" << endl;
    } else {
        cout << maxVisitor << endl << count;
    }

    return 0;
}
반응형