[BOJ / C++] 1806번 : 부분합

문제

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

입력

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

출력

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

Solved.ac 레벨

골드 IV

풀이

오랜만에 풀어보는 투 포인터 문제.

골드 4 문제 치고는 크게 어렵지 않다고 느껴졌다. 

시작 포인트 (start)와 끝 포인트 (end)를 같은 0에서부터 시작해서 연속된 수들의 부분합이기 때문에 start <= end와 end < n을 유지할 때 탐색을 하면 된다.

 

먼저 누적 합은 수열의 맨 처음으로 초기화시킨 뒤 탐색을 해줬다.

 

1. start ~ end의 합이 S보다 작다.

만약 start = 1이고 end = 3이라면 end를 4로 늘려서 1 ~ 4까지의 범위로 늘려서 판단해봐야 한다.

 

2. start ~ end의 합이 S보다 크거나 같다.

현재까지의 길이, 그리고 기존에 저장되어 있던 길이와 비교하여 현재까지의 길이가 더 작다면 갱신을 해준다.

또한 start를 앞으로 당겨서 범위를 줄여보아야 한다.

 

end를 전위증가, start를 후위증가 시킨 이유로는 end는 다음 인덱스의 값을 현재 합에 포함시켜야 하므로 인덱스를 먼저 증가시켜 다음의 값을 먼저 더하고, start는 현재 인덱스의 값을 현재 합에 포함시켜야 하므로 현재 합에 현재 인덱스의 값을 빼준 후 start를 앞으로 당겨야 하기 때문이다.

 

Code

#include<bits/stdc++.h>
#define INF 987654321

using namespace std;

int n, s;
vector<int> v;

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

    cin >> n >> s;

    for(int i = 0; i < n; i++) {
        int num;
        cin >> num;
        v.push_back(num);
    }


    int start = 0, end = 0, sum = v[0], len = INF;

    while(start <= end && end < n) {
        if(sum >= s) len = min(len, end - start + 1);
        if(sum < s) {
            sum += v[++end];
        } else {
            sum -= v[start++];
        }
    }

    if(len == INF) {
        cout << 0 << "\n";
    } else {
        cout << len << "\n";
    }


    return 0;
}

1806번: 부분합