백준 문제 24499번 blobyum 문제풀이 c++

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

24499번: blobyum

 

문제해석

 

 

누적합 문제임을 쉽게 알아 차리는것이 가능한데 단, 선형이 아닌 원형임을 인지하고있어야한다.

그래서 N의 입력이 최대 100000이므로 그것의 두배 정도의 배열에 누적합을 저장해놓으면 메모리의 낭비는 생기지만

편하게 코드를 작성 할 수있다.

어렵지 않으므로 별도의 설명없이 코드만 보아도 쉽게 이해 가능할 것 같다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
int a[200002];
int sum[200002];
int ans=0;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    for(int i=1; i<=n; i++)
    {
        a[i+n]=a[i];
    }
    sum[1]=a[1];
    for(int i=2; i<=2*n; i++)
    {
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=k; i<=2*n; i++)
    {
        ans=max(ans,sum[i]-sum[i-k]);
    }
    cout<<ans;
}