[백준] 1806번 : 부분합 (C++)

1806번 : 부분합

---

문제)

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

 

 

 

입력 :

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

 

 

 

출력 :

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

 

 

 

 

 

풀이)

// 1806. 부분합
#include <iostream>
#include <vector>
#include <limits.h>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    long long m;
    cin >> n >> m;
 
    vector<int> vec(n);
    for (int& ele : vec) cin >> ele;
    vec.push_back(0); // 패딩 처리
 
    int s = 0;
    int e = 0;
    // 첫번째 인자를 미리 더해놓는다.
    long long _sum = vec[0];
 
    int ans = INT_MAX;
    while (e < n)
    {
        // 조건을 만족할 경우 최단 거리를 ans로 설정한다.
        if (_sum >= m) ans = min(ans, e - s + 1);
 
        // 부분 합 중 s 이상이 된다면, 그 순간이 s부터의 합 중
        // 최단 길이이므로, s를 옮겨준다.
        if (_sum >= m)
        {
            _sum -= vec[s];
            s++;
        }
        else if (_sum < m)
        {
            e++;
            _sum += vec[e];
        }
    }
 
    // 만약 ans에 변화가 없다면, 그러한 합을 만들 수 없으므로
    // 0을 출력한다.
    if (ans == INT_MAX) cout << 0;
    else cout << ans;
    
    return 0;
}
 

---

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

1806번: 부분합