[틀림] 백준 2018 수들의 합 5 // 투포인터, 배열없는, n=천만이면 O(N)

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

* 시도1

• 누적합만들고
• 이진탐색으로 찾으면 될듯?
• 메모리초과 (1천만배열)
• 시간초과 (n log 1천만 ) == 천만 * 23 -> 23억
• o(N)에 풀어야한다.

 

* 풀이

• 이문제는 메모리제한이 32MB -> 1천만 배열불가능
• s,e가 index인 동시에, 값의 역할도 해야함!

• 엣지케이스 확인
  
  • n=1 ) break문에 걸려서 잘처리됨
  • 마지막 부분 해보기
    • break에 걸려서 자기자신이 카운팅이 안됨 -> ret=1 로 시작

#include<bits/stdc++.h>
using namespace std; 

typedef long long ll;

ll n,ret;

int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

   cin>>n;
   // v.push_back(0); // 1-idx로 만들기
   // for(int i=1;i<=n;++i) {
   //    v.push_back(i);
   // }

   // if(n==1) {
   //    cout<<1;
   //    return 0;
   // }
   
   // for(int i=1;i<=n;++i) {
   //    v.push_back(i);
   // }

   // s,e가 값의 역할도 하도록 개선!
   ll s=1; 
   ll e=2; //안포
   ret=1; //자기자신 기본값
   ll sum=1;
   while(1) {
      if(e==n+1) break;
      if(sum == n) {
         ret++;
         sum+=e;
         e++;
      }
      else if(sum>n) {
         sum-=s;
         s++;
      }
      else {
         sum+=e;
         e++;
      }
   }
   cout<<ret;
   
   return 0;
}