문제

문제분석

먼저 구간 합을 구해야한다.
prefix sum vs segment tree 뭐가 좋을까?
업데이트 없이 조회만 하면 된다. 조회 시간이 O(1)인, prefix sum을 사용하는 것이 좋을 것이다.

다음으로, 구간 합의 경계인 l 과 r을 찾아야한다.
naive한 방법은 nC2 경우를 모두 조사하는 것이다. 조합을 찾는데만 시간 복잡도는 O(N^2)으로 불가능하다.

대체 방법으로는 각 l 에 대하여 가장 가까운 r을 찾는 것이다. 이때, naive하게 찾는 것이 아니라 binary search 느낌으로 찾을 수 있다. 시간 복잡도는 O(NlogN)이 된다.

더 나은 방법으로는 two pointer 방식을 쓰는 것이다. 시간 복잡도는 O(N)이 된다.
이때 대부분의 경우 l은 왼쪽 끝, r은 오른쪽 끝에서 시작하지만, 여기에선 l과 r 모두 왼쪽에서 시작해서 loop마다 조정해야 한다.

알고리즘

binary Search
or
Two pointer

자료구조

prefix sum array

결과

/*
binary search
*/
#include <iostream>
#include <vector>

using namespace std;

const int MAX_INT = ~(1<<31);
const int MAX_N = 100000;

int N, S; // N: size of array, S: target sum
vector<int> prefixSum(MAX_N+1, 0); // idx: [0, N], arr[0]: padding

int main( void )
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> N >> S;
    {
        int val;
        for ( int i = 1; i <= N; i++ ){
            cin >> val;
            prefixSum[i] = prefixSum[i-1] + val;
        }
    }

    int minLength = MAX_INT;
    for ( int l = 0; l <= N; l++ ){
        int r = N;
        int prevR = N;
        while ( r > l ){
            if ( prefixSum[r] - prefixSum[l] >= S ){
                if ( minLength > (r-l) )
                    minLength = r - l;
                prevR = r;
                r = (r-l) / 2 + l;
            }
            else{
                int newR = (prevR - r )/ 2 + r;
                if ( newR == r )
                    break;
                r = newR;
            }
        }
    }

    if( minLength == MAX_INT )
        cout << 0;
    else 
        cout << minLength;

    return 0;
}

/*
two pointer
*/
#include <iostream>
#include <vector>

using namespace std;

const int MAX_INT = ~(1<<31);
const int MAX_N = 100000;

int N, S;
vector<int> prefixSum(MAX_N+1, 0);

int main (void )
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> N >> S;
    for ( int i = 1; i <= N; i++ ){
        cin >> prefixSum[i];
        prefixSum[i] += prefixSum[i-1];
    }

    int minLength = MAX_INT;
    {
        int l = 0, r = 0;
        while ( l <= N && r <= N ){
            int sum = prefixSum[r] - prefixSum[l];
            if ( sum < S )
                r++;
            else { // sum >= S
                minLength = minLength > r - l ? r - l : minLength;
                l++;
            }
        }
    }

    if ( minLength == MAX_INT )
        cout << 0;
    else 
        cout << minLength;

    return 0;
}

Other

binary search로 한 번 조사하는 건 O(logN)으로 빠르지만, l이 N개가 가능하므로 O(NlogN)이 된다. 이런 경우 two pointer가 더 낫다.

2467. 용액 의 경우도 비슷하다.