[백준] 1806 : 부분합

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

1806번: 부분합

---

• 수열에서 연속된 숫자들의 부분 합을 구하기 때문에, 왼쪽 인덱스부터 오른쪽 인덱스까지의 부분합을 인덱스를 움직여가면서 확인할 수 있다.
• 원래는 배열을 두고 양쪽 위치에 대한 인덱스를 조정하면서 검사하지만, 큐를 사용해 보았다.
• 수열을 큐로 저장해나가면서 해당 큐에 들어있는 원소들의 전체 합을 갱신시켜준다.
• 현재 수열의 부분합이 S 를 넘어갈 경우 앞에 있던 원소들부터 빼주는 식으로 양쪽 포인터를 관리한다.

---

#include <iostream>
#include <queue>

using namespace std;

int N, S, total, temp, answer=100000;

int main(void)
{
    cin >> N >> S;
    queue<int> q;
    for(int i = 0 ; i < N ; i++)        // 수열의 수들을 하나씩 입력받으면서
    {
        cin >> temp;
        q.push(temp);                   // 큐에 넣어주고
        total += temp;                  // 부분합을 업데이트해줌
        while(total >= S)               // 만약 현재 큐의 원소들의 합(부분합)이 
        {
            if(q.size() < answer) answer = q.size();    // 현재 부분합이 최소 길이일 경우 갱신
            total -= q.front();         // 앞의 원소를 제외해줌
            q.pop();                    // 제외한 수열의 부분합이 여전히 S 보다 클 경우 반복
        }
    }
    cout << (answer == 100000 ? 0 : answer) << endl;
}