[BOJ/C++] 부분합(1806번)

1. 개요

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

1806번: 부분합

1-1. 설명

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

1-2. 제한 사항

 - 첫 줄에 N과 S가 주어지며, N은 1 이상 100,000 이하, S는 1 이상 100,000,000 이하

 - 둘째 줄에는 수열이 주어짐

---

2. 구현

2-1. 풀이

투 포인터를 이용하여 구현하였다. 부분합이 S와 동일하거나 클 때, 길이를 구해 현재 길이와 구한 길이의 최소를 저장해주었다. 

2-2. 코드 

#include <iostream>
#include <algorithm>
using namespace std;

constexpr size_t MAX_NUM = 100000;
int nums[MAX_NUM];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, S, len = 100000001;
    cin >> N >> S;

    for (int i = 0; i < N; i++) cin >> nums[i];
    int start, end = 0, curSum = 0;
    for (start = 0; start < N; start++) {
        while (curSum < S && end < N) curSum += nums[end++];
        if (curSum >= S) len = min(len, end - start);
        curSum -= nums[start];
    }
    if (len == 100000001) len = 0;
    cout << len;
    return 0;
}