백준 1806 부분합 c++ // 투포인터, 누적합 구현방법

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

1806번: 부분합

1. 문제

누적합배열을 썻더니 오답이 나왔다.

최적해를 보장하지 않는것 같다.. (정렬이 안되서?)

 

1.1 해결 : tot 변수를 써서 누적합을 저장함

 

2. 의사코드 

1. total보다 S가 크면, en을 하나 늘려주고 total 변수에 arr[en]을 더한다. 
    (쉽게말해 total을 st~en -> st~en+1로 만드는 것)

2. total보다 S가 작으면, total 변수에 arr[st]를 빼고 st를 하나 늘려준다.
    (쉽게말해 total을 st~en -> st+1~en로 만드는 것)

 

3. 전체코드

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/ecc7d7f58ceb4679a1bb67adbb79088c
#include <bits/stdc++.h>
using namespace std;

int n, s, tot;
int a[100005];
int mn = 0x7fffffff;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s;
    for (int i = 0; i < n; i++) cin >> a[i];
    tot = a[0];
    int en = 0;
    for (int st = 0; st < n; st++) {
        //tot<s 인경우 : en++, tot++ (st~en+1)로 만들기
        while (en < n && tot < s) {
            en++;
            if (en != n) tot += a[en];
        }
        if (en == n) break; //out of index check
        
        //tot>=s 인경우 : 정답갱신, tot-- (st+1~en)으로 만들기
        mn = min(mn, en - st + 1);
        tot -= a[st];
    }
    if (mn == 0x7fffffff) mn = 0;
    cout << mn;
}