[Algorithm] Baekjoon 1806번 : 부분합

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

1806번: 부분합

#define MAX_NUM 100000
int minNum = MAX_NUM;
int arr[100001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, s;
 
    cin >> n >> s;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    int left = 0;
    int right = 0;
    
    int sum = arr[0];
 
    while (right < n)
    {
        if (sum >= s)
        {
            minNum = min(minNum, right-left);
 
            if (left == right)
            {
                ++right;
                sum += arr[right];
                continue;
            }
 
            sum -= arr[left];
            ++left;
        }
        else
        {
            ++right;
            sum += arr[right];
        }
    }
 
    if (minNum == MAX_NUM)
    {
        cout << 0;
    }
    else cout << minNum + 1;
}

부분합의 가짓수를 만들어가며 m이상인 경우 최소의 길이를 구하는 문제이다.

여기서 '길이'라는것은 부분합의 원소갯수를 말한다.

그리고 문제에는 따로 명시가 안되어 있는데, 이 '길이'는 최소 1이상이다.

즉 원소 1개만 선택되는 경우도 가짓수로 치기 때문에 이부분만 명심하면 된다.

 

그래서 처음 left,right를 0으로 하고 sum을 arr[0]값으로 해줬다.

실수하지 말아야 할 것은 1개만 선택한 것이기 때문에 초기 sum값을 arr[left] + arr[right] 처럼 하면 안된다.