백준 1806번 부분합(C++)

시간초과 

#include<vector>
#include <iostream>
#include<algorithm>

using namespace std;

int main()
{

   int n,s; 
   //길이가 가장 짧으면서 s이상인거 
   
   cin>>n>>s; 
   vector<int>arr;
   arr.assign(n+1,0);
   for(int i=1;i<=n;i++){
       cin>>arr[i]; 
       arr[i]+=arr[i-1];
   }
   
   //1...n개짜리 길이 
   
   for(int i=1;i<=n;i++){//100,000
       
       if(arr[i]>=s){
           cout<<1; return 0; 
       }
       for(int j=0;j<=n-i;j++){ //100,000
           int sum=arr[j+i]-arr[j]; 
           
           if(sum>=s){
               cout<<i; return 0;
           }
       }
       
       
   }
   
   cout<<0;
   
    return 0;
}

 

맞았습니다.

누적합으로 합더하고 합이 크면 left++, 작으면 right++

#include<vector>
#include <iostream>
#include<algorithm>

using namespace std;

int main()
{

   int n,s; 
   //길이가 가장 짧으면서 s이상인거 
   
   cin>>n>>s; 
   vector<int>arr;
   arr.assign(n+1,0);
   for(int i=1;i<=n;i++){
       cin>>arr[i]; 
       arr[i]+=arr[i-1];
   }
   
   //1...n개짜리 길이 
   int left=1;
   int right=1; 
   
   int mins=10000000;
  
   while(left<=right && right<=n){
       
       int len=right-left+1;
       
       int sum=arr[right]-arr[left-1];
       
       if(sum>=s){
           mins=min(mins,len);
           left++;
       }
       else{
           right++;
       }
       
   }
   if(mins==10000000)cout<<0;
   else cout<<mins;
   
    return 0;
}