1806 부분합

 

무난하게 풀었다.

배열의 요소가 10,000이하이고 길이가 100,000이라 합 구하다가 100퍼 터지기 때문에 합은 long long으로 만들어줬다.

 

#include <iostream>
#include <vector>
using namespace std;
using i64 = long long;

int main() {
    int n, s;
    scanf("%d %d", &n, &s);
    vector<int> v(n);
    
    i64 allSum = 0;
    for(int i = 0; i < n; i++){
        scanf("%d", &v[i]);
        allSum += v[i];
    }
    
    int l = 0, r = 0;
    int ans = n;
    int count = 1;
    i64 sum = v[0];
    
    while(l < n){
        if(sum < s){
            if(r == n-1)
                break;
            sum += v[++r];
            count++;
        }
        else {
            if(count < ans)
                ans = count;
            sum -= v[l++];
            count--;
        }
    }
    if(allSum < s)
        printf("0");
    else
        printf("%d", ans);
    
    return 0;
}

 

 

 

---

좀 더 깔끔한 코드!

 

allSum은 ans로 확인할 수 있어서 없애고

count 변수도 r-l로 구할 수 있음 

 

 

보통 반복문 두번이면 O(n^2)이라 생각하는데 신기하게 코드 들여다보면 선형임. 오...