백준 1806번 부분합

부분합 

0.5 초 (하단 참고)

128 MB

29040

7511

5344

25.557%

문제

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

입력

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

출력

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

이중포문을 쓰려다가 투포인터 기본문제라고 해서 투포인터를 사용해 풀어보았다. 알아보니 기존 이중포문을 사용하면 시간복잡도가 O(N^2)이지만 투포인터를 쓰면 O(N)에 풀수 있다고한다!

 

while루프를 돌면서, total이 S 이상일 경우 길이(end-st+1)확인 후 최솟값이면 저장한다.(st가 end보다 커지거나, end이 끝에 도달하면 탈출)

total보다 S가 크면, end을 증가시키고 total 변수에 v[end]을 더한다. 

total보다 S가 작으면, total 변수에 v[st]를 빼고 st를 증가시킨다.

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


int main() {
    int n;
    long long s;
    cin >> n >> s;
    vector<int> v(n+1);
    for(int i=1; i<=n; i++){
        cin >> v[i];
    }
    int st = 1;
    int end = 1;
    int total = v[1];
    //정답배열 길이
    int ans=987654321;
    while(st <= end && end <= n){
        if(total>=s){
            ans = min(ans,(end-st+1));
            total -= v[st];
            st++;
        }else if (total <s) {
            end++;
            total += v[end];
        }
    }
    if(ans == 987654321) {
        cout << "0";
        
    }else{
        cout << ans;
    }

    return 0;
    
}