백준 2003번: 수들의 합 2 (C++)

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

n이 10000 이하이고, 시간 제한이 0.5초이기 때문에, n^2 풀이로 풀게 되면 시간 초과가 날 것이다.

따라서 O(n)에 해결할 수 있도록 투포인터를 사용하도록 한다.

초기에 st와 en을 모두 시작점으로 정해두고, en이 범위 밖으로 벗어날 때까지 진행해준다.

#include<iostream>
 
using namespace std;
int n, m, arr[10001];
int main(void) {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
 
    int st = 0, en = 0, cnt = 0;
    long long Sum = arr[0];
 
    while (1) {
        //합이 부족해서 en이 우측으로 움직이는 건데, en이 밖으로 나갔다는 것은 더 볼 필요가 없다는 것
        //st가 우측으로 움직여봤자 합은 더 감소하기 때문에
        if (en >= n) break; 
        
        if (Sum == m) {
            Sum += arr[++en]; //딱 만족할 때 en 증가
            cnt++;
        }
 
        else if (Sum < m) Sum += arr[++en];
 
        else {
            
            Sum -= arr[st++];
            if (st > en) {
                en = st;
                Sum = arr[en];
            }
        }
    }
    cout << cnt;
    return 0;
}