백준 14246번 K보다 큰 구간 [C++]

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

14246번: K보다 큰 구간

문제 간단 정리

구간합으로도 될 것 같다. 하지만 투 포인터로 풀어보자 

만약 12345 이고 K가 5일때

현재 123을 합한상태라면 4 5 는 더할 필요 없이 +3만 해주면 된다. 

이를 유의해서 풀

문제 해결 방법

투 포인터를 이용해서 풀어보자..

인덱스를 조심해야된다

전체 코드

#include<vector>
#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
    ll N, M;
    vector<ll> cnt;
    cin >> N ;

    for (int i = 0; i < N; i++) {
        ll input;
        cin >> input;
        cnt.push_back(input);

    }
    cnt.push_back(0); //인덱스 때문에 하나 추가

    cin >> M;


    ll count = 0;
    ll start = 0; ll end=0;
    ll sum = cnt[start];

    while (1) {

        if (sum > M) { //합이 클때

            sum -= cnt[start];
            count += N - end;

            
            if (start == end) {
                end++;
                sum += cnt[end];
            }
            start++;

        }
        else if (sum <= M) { //합이 적을때

            end++;
            sum += cnt[end];
            
        }
        if (end == N) break;

    }

    cout << count;
}