[BOJ / C++] 부분합 (투포인터)

문제링크: https://www.acmicpc.net/problem/1806

 

1. 코드

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

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

    int n, s;
    cin >> n >> s;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int mn = INT_MAX;
    int en = 0;
    int sum = arr[0];

    for (int st = 0; st < n; st++) {
        while (en < n && sum < s) {
            en++;
            if (en != n) sum += arr[en];
        }
        if (en == n) break;
        mn = min(mn, en-st+1);
        sum -= arr[st];
    }
    if (mn == INT_MAX) mn = 0;
    
    cout << mn;
}

 

 

2. 시간복잡도

n = 100,000 이므로 O(n^2)은 안된다. 투 포인터를 이용하면 O(2n)에 해결할 수 있다. n = 100,000 < 10^7 이므로 시간제한 0.5초 내에 해결가능하다.

 

 

3. 분석

sum이라는 변수를 두고 sum < s까지 en을 증가시켜서 sum > s인 en을 찾고 mn을 업데이트 해준 후 다음 iteration에 st를 증가시킬거기 때문에 sum -= arr[st]를 해준다. 

 

합을 만들 수 없으면 0을 출력하는 조건도 신경써준다.