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

[ BOJ ] 21921번 : 블로그

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

---

[  문제  ]

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

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

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

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

[  입력  ]

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

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

[  출력  ]

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

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

 

[  제한  ]

• $1 \le X \le N \le 250,000$ 
•  $0 \le$ 방문자 수 $\le 8,000$ 

---

[  문제 접근 및 풀이  ]

$X$가 25만이고, 방문자 수가 8천명이라고 가정했을 때

최댓값은 20억으로 int형의 최댓값은 21억 정도로 넘지 않는다.

투 포인터(Two-Pointer) 알고리즘으로 1일부터 X일동안 들어온 방문자를 psum 변수에 넣어주고

1일차 ~ X일차 , 2일차 ~ X+1일차, 3일차 ~ X+2일차 ...의 값을 구하면서

최댓값을 넘는다면 Maxvalue값을 바꿔주며 Maxcnt를 1로 바꾸어준다.

또한 최댓값과 같다면 기간을 1일 추가한다.

 

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
int X,N,Maxvalue=0,Maxcnt=0;
int arr[250001];
void Q_21921();
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Q_21921();
}
void Q_21921(){
    cin >> N >> X;
    for(int i=0;i<N;i++){
        cin >> arr[i];
    }
    int st=0,ed=X-1,psum=0;
    for(int i=0;i<X;i++)psum+=arr[i];
    while(ed<N){
        if(Maxvalue<psum){
            Maxvalue=psum;
            Maxcnt=1;
        }
        else if(Maxvalue==psum) Maxcnt++;
        psum-=arr[st++];
        psum+=arr[++ed];
    }
    if(!Maxvalue) cout<<"SAD";
    else cout << Maxvalue << "\n" << Maxcnt;
}

---