[C++] BOJ 21921번 : 블로그

 

 

 

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

 

문제 3줄 요약

1. 운영하고 있는 블로그의 방문 기록이 있다.

2. 블로그의 X일 동안 가장 많이 들어온 방문자 수와 그 기간을 알고싶다.

3. 최대 방문자 수가 0이라면 "SAD" 슬픔을 표현하자

 

---

 

이번 문제는

이중 포인터를 활용한 문제이다.

 

방문자 수를

X일 동안의 방문자 수를 일자 별로 구해주기 보다는

1일차 부터 X일 동안 더해준 값을 기반으로

2일차 ~ 2+X일의 값을 구해주려고 했다.

 

 

말로는 어려우니 예시와 그림을 통해 살펴보자.

 

 

총 5일 간의 방문 기록 중

2일 간 방문자의 수가 최대였을 때, 방문자의 수와 기간은 어떻게 될까?

 

 

 

 

 

정답은 3일 ~ 4일차 까지의 방문자 수 합인 7과

방문자 수가 7인 기간이 하루 뿐이므로 1이 되겠다.

 

 

이때 방문자 수의 합을 매일 매일 구해주기 보다는

2일차에서는

1일차에서 구했던 합 5에서

첫 날의 방문자수를 빼주고 3일차의 방문자 수를 더해주면 더욱 효율적이겠다.

 

 

위와 같이 고정된 범위를 이동하며

범위 내의 값들을 활용하는 것을 슬라이딩 윈도우라고 한다.

 

 

 

물론 해당 예시는

2일 간의 방문 기록이므로 큰 차이가 없게 느껴지겠지만

X의 범위가 1이상 25만 이하이므로

그 길이가 길어질수록 위의 방법이 반복적인 연산 없이

기간 내의 합을 구해줄 수 있을 것이다.

 

 

코드로 아래와 같이 작성해보았다.

 

    // 1일차 ~ X일차를 초기값으로 설정한다.
    int answer = 0;
    for(int i=0; i<x; i++) answer += visit[i];

	// 2일차부터 비교를 하며 갱신한다.
    int* cnt = visit+1;
    int max_cnt = answer, duration = 1;

    for(int i=0; i<(n-x); i++)
    {
        max_cnt -= *(cnt-1);
        max_cnt += *(cnt+x-1);
        cnt++;

        if(answer == max_cnt) duration++;
        else if(answer < max_cnt)
        {
            answer = max_cnt;
            duration = 1;
        }
    }

 

 

1일차부터 X일 동안의 값을 초기값으로 정해주고,

인덱스를 통한 배열의 값을 받아오는 것이 아닌

포인터를 통해 배열의 값들을 받아오며, 일자별로 이동을 한다.

 

 

그림의 예시처럼

전날의 방문자수를 빼주고 기준일로부터 X일 이후의 방문자수를 더해주어

i 일자 ~ (i+x-1) 일자의 방문자수 총합을 구한다.

 

 

이후

최대 방문자 수를 찾기 위해

초기값과 비교해가며 최대 값을 갱신해나간다.

 

 

최대 값을 갱신했다면 기간 또한 초기화 해주며,

최대 값과 똑같은 기간이 발생했다면 기간을 늘려준다..!

 

최대 값이 0이라면 "SAD"를 출력하고,

기간은 생략하도록 한다!!

 

 

따라서

정답은 아래와 같이 작성할 수 있겠다.

 

#include <iostream>

using namespace std;

int visit[250'001];

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음

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

    for(int i=0; i<n; i++) cin >> visit[i];

    int answer = 0;
    for(int i=0; i<x; i++) answer += visit[i];

    int* cnt = visit+1;
    int max_cnt = answer, duration = 1;

    for(int i=0; i<(n-x); i++)
    {
        max_cnt -= *(cnt-1);
        max_cnt += *(cnt+x-1);
        cnt++;

        if(answer == max_cnt) duration++;
        else if(answer < max_cnt)
        {
            answer = max_cnt;
            duration = 1;
        }
    }

    if(answer) cout << answer << "\n" << duration;
    else cout << "SAD";
    return 0;
}

 

---

 

슬라이딩 윈도우를 통한 누적합을 구하면

풀 수 있는 문제였다.

 

끝!