백준 2559 수열

hyoJeong·2021년 6월 19일
0

이번에 포스팅할 문제는 2559 수열이라는 문제입니다.
문제링크:https://www.acmicpc.net/problem/2559

사용한 알고리즘:이분탐색
사용한 이유: 먼저 브루트포스로 풀 수 있는지 확인했습니다. 확인해 보니 N의 범위가 100,000이하이기 때문에 이중 for을 사용하면 해당 문제의 시간제한인 1초를 넘게 됩니다.
이분탐색을 사용한 이유는 일단 시간 복잡도가 O(N)이기 때문입니다. 또한 투포인터를 사용해 연속 측정날을 넘게 되면 뒤쪽에서 오는 포인터가 하나 앞으로 당겨지고, 연속 측정날보다 같거나 작으면 먼저 시작한 포인터가 앞으로 가도록 풀었습니다.

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

int main(){
    
    cin.tie(0);
    cout.tie(0);
    std::ios::sync_with_stdio(false);
    
    
    int n,k;
    cin>>n>>k;
    vector<int>v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    
   
    int res=-2147000000;
    int cnt=0;
    int lt=0;
    int rt=0;
    while(1){
        
      
        //연속 측정수날보다 작은 경우 lt 늘리기
        if((rt-lt)>k) {
            cnt-=v[lt++];
        }
        //종료 조건
        else if(rt==v.size()){
            //연속 측정날수와 같다면
            if((rt-lt)==k){
                //값 비교하기
                res=max(cnt,res);
            }
                break;
        }
        //연속 측정날보다 작거나 같으면
        else if((rt-lt)<=k){
            //값 비교하기
            if((rt-lt)==k){
                res=max(cnt,res);
            }
            //rt인덱스 증가하기
            cnt+=v[rt++];
           
        }
       
        
       
        
        
        
        
        
    }
    
    
    cout<<res<<"\n";
    
    
    
    return 0;
}

0개의 댓글