[1806] 부분합

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

1806번: 부분합

<문제>

브루트포스로 풀 수 있을까? 구간 (s,e)를 정하고, s의 범위는 (1,n), e의 범위도 (1,n)정도이다.

고로 O(N^2)의 시간복잡도를 갖는다. 

N이 10만, 시간제한이 0.5초이므로 O(NlogN)이하의 시간복잡도를 가져야만 TLE없이 해결할 수 있다.

 

정렬을 한 후 -> O(NlogN) 이분탐색을 수행하면(logN) 시간내에 해결할 수 있을지는 모르지만, 이 문제는 입력되는 수열을 그대로 유지한 상태에서 탐색해야한다. 

 

그렇기에 이 문제는 투포인터를 통해, 불필요한 부분은 더 탐색하지 않도록 만들것이다. 

대략 아래의 경우의 수를 생각해볼 수 있을것이다. L, R은 둘다 0으로 초기화한다.

1) 구간 (L,R)의 합이 S 미만인 경우 

-> 합을 더 크게해야 하므로 R++

2) 구간 (L,R)의 합이 S 이상인 경우

-> 정답의 가능성이 있으므로 최적해를 업데이트한다. 이후 더 짧은 경우를 찾기 위해 L++

 

동시에, L가 R보다 오른쪽에 존재하지 않도록, L와 R이 범위를 벗어나지 않도록 만들어주는 부분을 추가하면 된다.

<소스코드>

#include<stdio.h>
#include<algorithm>
using namespace std;
int n, s;
int a[100001];
const int INF=2121212121;
int main(void) {
    int i, j,left,right,len=INF,min_len=INF,sum=0;
    scanf("%d %d", &n, &s);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        if (a[i] >= s) {
            printf("1");
            return 0;
        }
    }
    sum = a[0];
    left = 0;
    right = 0;
    while (left <= right && right <= n-1) {
        if (sum < s && right < n) {
            right++;
            sum += a[right];
        }
        else if (sum >= s) {
            len = right - left + 1;
            min_len = min(len, min_len);
            if (left <= right) {
                sum -= a[left];
                left++;
            }
        }
    }
    if (min_len == INF)printf("0");
    else printf("%d", min_len);
    return 0;
}