[백준 C++] 1806번 부분합

1806번: 부분합

문제 요약

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

사용 알고리즘

투포인터, 누적합

입출력

• 입력:
• 출력: ``` 예제1

입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

## 풀이
먼저 누적합을 사용하여 전체 누적합을 다 구한다. 이후 투포인터를 사용하는데 한개는 맨 앞, 한개는 그 바로 뒤에서 시작한다. 크기가 s보다 작으면 뒤의 포인터를 뒤로 보내고, s보다 크면 앞의 포인터를 뒤로 보낸다. 부분합은 누적합을 이용하여 쉽게 구한다. 만약 뒤의 포인터가 끝을 벗어난다면 그대로 끝내면된다. 그 상황에서 앞의 포인터가 뒤로 가도 s보다 커질 수 없기 때문이다.

## 어려웠던 점
투포인터를 시작할때 모두 앞에 두고 시작해야한다.

## 배운 점 / 느낀 점
투포인터를 사용한지 얼마 되지 않아 아이디어를 떠올리는데 오래걸렸다. 투포인터를 자유자재로 사용하기 위해 더 노력해야겠다.

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, s, m;
vector<int> sss;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> s;
    sss = vector<int>(n+1,0);
    m = n+1;

    for (int i = 1; i < n+1; i++) {
        cin >> sss[i];
        sss[i] += sss[i-1];
    }

    int l = 0;
    int r = 1;
    while(r < n+1){
        if(sss[r]-sss[l] >= s){
            m = min(m, r-l);
            l += 1;
        }
        else{
            r += 1;
        }
    }
    if(m == n+1){
        cout << 0;
    }
    else cout << m;
    return 0;
}