[1일 1알고] G4 1806 부분합

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

 

이번 문제는 투 포인터를 사용하는 문제입니다.

 

부분합을 보고 처음에는 1부터 시작해 부분합 범위를 점점 늘려가며 답을 찾아보려했습니다.

하지만 이 방법은 O(N^2)인데, 조건이 N이 최대 10만이고 시간 제한이 0.5초이기 때문에 이 방법은 불가했습니다.

 

따라서 O(N)방법인 투 포인터를 사용했습니다.

 

---

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <math.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, S;
    cin >> N >> S;
    vector<int> v(N, 0);
    
    long long sum = 0;
    for (int i = 0; i < N; ++i)
    {
        cin >> v[i];
        sum += v[i];
    }
    if (sum < S)
    {
        cout << 0;
        return 0;
    }
    sum = v[0];
    int left = 0, right = 1;
    int result = 100001;
    while (left < N)
    {
        if (sum < S )
        {
            if (right == N)
                break;
            sum += v[right++];
        }
        else
        {
            result = min(result, right - left);
            sum -= v[left++];
        }
    }
    cout << result;
    return 0;
}

 

아이디어를 떠올리는게 어렵고, 경계처리를 섬세하게 하지 않으면 실수할 확률이 높아보입니다.