백준 2018번 수들의 합5(C++)🚩

정답1.

n= 10000000 까지인데 n개짜리 배열 만들었다가 메모리 초과..

n/2+1 까지 확인하는것으로 변경하고 예외적으로 1,2는 n/2+1가 자기 자신까지 될수 있어서 2보다 큰 숫자들만 

자기 자신일 경우 +1 해주었다. 

#include<vector>
#include <iostream>

using namespace std;

int main()
{
   int n;
   cin>>n;
   int cnt=0; 
   
   vector<int>arr(n/2+2,0);
   
   for(int i=1;i<=n/2+1;i++){
       arr[i]=i;
       arr[i]+=arr[i-1];
   }
   
   int left=0;
   int right=1;
   
   while(left<right && right<=n/2+1){
       
       int sum=arr[right]-arr[left];
       if(sum==n){
           cnt++;
           left++;
       }
       else if(sum>n){
           left++;
       }
       else{
           right++;
       }
       
   }
   if(n>2)cnt++;
   cout<<cnt;

    return 0;
}

 

정답2

꼭 누적합으로 계산해야할까? 해서 단순히 끝을 포함하는지 안하는지 방식으로 구현

#include<vector>
#include <iostream>

using namespace std;

int main()
{
   int n;
   cin>>n;
   int cnt=0; 
   
   int left=1;
   int right=1; 
   int sum=1;
   
   while(left<=right && right<=n){
       
       if(sum==n){
           cnt++;
           sum-=left;
           left++;
       }
       else if(sum>n){
          sum-=left;
          left++;
       }
       else{
           right++;
           sum+=right; 
       }
   }
  
  cout<<cnt;
    return 0;
}